Mathematica Overflow[] error : Why and how-to bypass?

I never had an overflow error in Mathematica, the following happened.

I demo-ed the principle of RSA-encryption as follows:

 n = 11*13
 m = EulerPhi[n]
 e = 7
 GCD[e, m]
 d = PowerMod[e, -1, m]
 cipher2[m_String] := Map[Mod[#^e, n] &, ToCharacterCode[m]]
 decipher2[x_Integer] := FromCharacterCode[Map[Mod[#^d, n] &, x]]

 In[207]:= cipher2["StackOverflow"]
 decipher2[cipher2["StackOverflow"]]
 Out[207]= {8,129,59,44,68,40,79,62,49,119,4,45,37}
 Out[208]= StackOverflow

No problem sofar.

Then I changed the prime numbers to a more realistically, but still very moderate size.

 n = 252097800611*252097800629

 In[236]:= cipher2["StackOverflow"]
 decipher2[cipher2["StackOverflow"]]

 Out[236]= {27136050989627, 282621973446656, 80798284478113, \
 93206534790699, 160578147647843, 19203908986159, 318547390056832, \
 107213535210701, 250226879128704, 114868566764928, 171382426877952, \
 207616015289871, 337931541778439}

 During evaluation of In[236]:= General::ovfl: Overflow occurred in computation. >>

 During evaluation of In[236]:= General::ovfl: Overflow occurred in computation. >>

 Out[237]= FromCharacterCode[{Overflow[], Overflow[], Overflow[], 
   Overflow[], Overflow[], Overflow[], Overflow[], Overflow[], 
   Overflow[], Overflow[], Overflow[], Overflow[], Overflow[]}]

Question : Have I simply gone through the limits of Mathematica? Have I used an incorrect approach? What is the by-pass, if any ??

3 Answers

  1. Peter- Reply

    2019-11-13

    Try using PowerMod in the decyphering operation:

    n = 252097800611*252097800629;
    m = EulerPhi[n];
    e = 7;
    Print[GCD[e, m]];
    d = PowerMod[e, -1, m];
    Print[{"n" -> n, "m" -> m, "e" -> e, "d" -> d}];
    Grid[
     Join[{
      {"Input", "Encrypted", "Decrypt with Mod", "Decrypt with PowerMod"}}, 
      Table[{i, (j = Mod[i^e, n]), Mod[j^d, n], PowerMod[j, d, n]}, {i, 40}]], 
     Frame -> All]
    
  2. Philip- Reply

    2019-11-13

    Yes, you have gone through the limits of Mathematica. The maximum number that can be represented on a system in a particular version of Mathematica is shown by $MaxNumber. In your second example, d=18158086021982021938023 and hence 27136050989627^d is way way larger than $MaxNumber.

    You can use PowerMod in the second step too like you did for d, which will compute a^b mod n more efficiently than Mod. With decipher2[x_List] := FromCharacterCode[Map[PowerMod[#, d, n] &, x]], you get:

    cipher2["StackOverflow"]
    decipher2[cipher2["StackOverflow"]]
    
    Out[1]= {27136050989627, 282621973446656, 80798284478113, \
    93206534790699, 160578147647843, 19203908986159, 318547390056832, \
    107213535210701, 250226879128704, 114868566764928, 171382426877952, \
    207616015289871, 337931541778439}
    
    Out[2]= "StackOverflow"
    
  3. Phoebe- Reply

    2019-11-13

    Yep, as the other guy answered you have well and truly reached the $MaxNumber Mathematica can handle.

    There is a bypass which will find mod for many large numbers larger than $MaxNumber.

    Rather than imputing large numbers directly into Mathematica, such as 163840000000^18158086021982021938023 which is absolutely huge, use Modular arithmetic to save Mathematica the trouble of having to compute such a large number.

    You should be able to develop a Mathematica Code for this, I do not yet know how to do this. But you can do it by hand, by finding: Mod[Mod[Mod[Mod[Mod[Mod[Mod[Mod[163840000000^181,n]^580,n]^860,n]^219,n]^820,n]^219,n]^380,n]^23,n]

    Which gives the correct answer you are looking for, without exceeding $MaxNumber

Leave a Reply

Your email address will not be published. Required fields are marked *

You can use these HTML tags and attributes <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>