Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Dealing With Overflow?

  1. #1
    Junior Member
    Join Date
    Apr 2013
    Posts
    2
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default 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!


  2. #2
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Dealing With Overflow?

    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

Similar Threads

  1. Recursive method - stack overflow
    By yakir_g in forum What's Wrong With My Code?
    Replies: 4
    Last Post: April 8th, 2013, 07:38 AM
  2. [SOLVED] Banker Deadlock detection algorith going haywire and likely a stack overflow error
    By javapenguin in forum What's Wrong With My Code?
    Replies: 2
    Last Post: April 23rd, 2012, 05:23 PM
  3. [SOLVED] stack overflow error
    By Goldfinch in forum What's Wrong With My Code?
    Replies: 14
    Last Post: February 3rd, 2012, 01:07 AM
  4. Help with code dealing with parallel arrays.
    By danielp1213 in forum What's Wrong With My Code?
    Replies: 5
    Last Post: November 13th, 2011, 07:43 PM
  5. Replies: 0
    Last Post: October 14th, 2008, 06:40 PM