Thread: Dealing With Overflow?

Hi,

Does anyone know a short code that prevents overflow when using encryption? I don't understand what my professor means by this. I asked him if we could round or just cut off so many numbers and he said no to both...? So maybe someone else understands what he's asking? I know we need to use a loop which is why I posted it into this forum. Thanks!

I'll take a shot.

First, I must uncover my crystal ball. Stand back, sometimes it gets a little rowdy...

OK! So far, so good. Apparently Mr. XtalBall is having a good day (so far).

My crystal ball tells me that you are studying some kind of encryption algorithm (maybe RSA or some such thing) that requires calculations like

c = (b to the power a) modulo m

Where b is a positive integer value (maybe something like a character that is part of the encryption input stream), and a and m are the two prime factors of your encryption key.

Now, in "real" encryption projects, a and m are very large numbers. So large that you need BigInteger (or some other arbitrary precision integer class) data types even to represent them, let alone do arithmetic with them.

For "toy" problems like in a classroom example or assignment, maybe a and m have sizes that can be represented with built-in Java integer data types.

Now, since the result is modulo m, that means the result can take on values 0, 1, ..., m-1, so the result can also be represented with built-in Java integer data types. The question is whether we can calculate c with built-in data types without overflowing.

First we note that a naive implementation of the formula can result in overflow.

For example:
Suppose b is equal to 99 and a is equal to 577 and m is equal to 641.

Now a naive implementation that tries to raise 99 to the power 577 will certainly fail (due to overflow) for arithmetic using Java built-in data types.

After all, (99 to the power 577) is something like

303045111570971263955821820392696178143265758724474467938624798116339577288162485116030733099263709965572958181906924399253021380548046259101517780965524393547584864422343135686897420839537466317307515804972133702404927217398649647923411948352111409372874694450433844639206281252894855929204415750651515441208488460200330778079283908520077566533369200618391401173983176318050299322833025784646723586631353696713395419023408530554378399550582831806939016214938513107859102700415324451413372272361242272995532935900311460113227961427508757362116707499725851999665692159966097062026101024784387089061967879036208523443964341720488977845563106860585855919454454864047261703716290937407555673997293641593529531385878567222149153028244921196301928117121778763244410687262712368049414194431738953931635524152073516621124252074457255276600258168584622233356923542938899399391203538142610264898518470694650596886677706137720761344760825372452193480233433965492113866178438799904396284740563513356276554384143820319002669191614951869265557391055759121962675288924338737987946937091889830549869806058638439348725913062637837585573651668893292318940629008738297699

That's 1152 decimal digits if anyone is counting.

Now, instead of immediately reaching for the BigInteger package, we can investigate other ways of calculating (b to the power a) modulo m. My crystal ball tells me that that is really the assignment. (But my crystal ball is only 99 and 44/100 percent correct, so it could be wrong.)

Anyhow...

One extremely simple way is given in the Wikipedia article on Modular Exponentiation

The pseudo-code for the Memory Efficient method can be implemented with a grand total of seven lines of java (five lines of actual code).

public class Z {
    public static void main(String [] args) {
        int b = 99;
         a = 577;
        int m = 641;
        long x = powMod(b, a, m);
        System.out.printf("powMod(%d,%d,%d) = %d\n", b, a, m, x);
    } // End main
 
    static long powMod(int base, long exponent, long modulus) {
        // ...
        // Five lines of Java from the pseudo-code in the Wikipedia article
        // on Modular Exponentiation
        // ...
    } // End powMod
 
} // End class definition

Result:

powMod(99,577,641) = 88

For testing your powMod function, you can use smaller values of a and b so that the naive implementation won't overflow.

So...
Calculate with the naive implementation for these small values, then plug into your function and make sure you get the same result.

Then try my example (or others that you can find on the web) with your very own powMod function.

Finally (yes, it's coming to an end), note that the algorithm that I pointed to is extremely simple to implement, and with the explanation in Wikipedia, maybe even easy to understand.

There are other almost-as-easy-to-implement algorithms that are, perhaps, more efficient and for some people still fairly understandable. (The Russian peasant algorithm is popular in elementary courses.)


Cheers!

Z