Error de Overflow [] de Mathematica: ¿Por qué y cómo omitir?

Question

Nunca tuve un error de desbordamiento en Mathematica, sucedió lo siguiente.

I DEMO-ED el principio de cifrado RSA-de la siguiente manera:

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 hay problema sofar.

Luego cambié los números primos a un tamaño más realista, pero aún muy moderado.

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[]}] 

Pregunta: ¿Yo simplemente pasado por los límites de Mathematica? ¿He usado un enfoque incorrecto? ¿Qué es el by-pass, si hay alguno?

Answer 1

Intente utilizar PowerMod en la operación de desciframiento:

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] 

Answer 2

Sí, han pasado por los límites de Mathematica. El número máximo que se puede representar en un sistema en una versión particular de Mathematica se muestra en $MaxNumber. En su segundo ejemplo, d=18158086021982021938023 y por lo tanto 27136050989627^d es mucho más que $MaxNumber.

Puede utilizar PowerMod en el segundo paso demasiado igual que lo hizo para d, que computar a^b mod n más eficiente que Mod. Con decipher2[x_List] := FromCharacterCode[Map[PowerMod[#, d, n] &, x]], se obtiene:

cipher2["StackOverflow"] 
decipher2[cipher2["StackOverflow"]] 

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

Out[2]= "StackOverflow" 

Answer 3

Sí, como el otro chico respondió que haya bien y verdaderamente alcanzado los $ MAXNUMBER Mathematica puede manejar.

Hay un bypass que encontrará mod para muchos números grandes de $ MaxNumber.

En lugar de imputar números grandes directamente a Mathematica, como 163840000000^18158086021982021938023, que es absolutamente enorme, utilice la aritmética modular para ahorrarle a Mathematica el problema de tener que calcular un número tan grande.

Debería poder desarrollar un Código de Mathematica para esto, todavía no sé cómo hacerlo. Pero puede hacerlo a mano, encontrando: 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]

que da la respuesta correcta que busca, sin exceder $ MAXNUMBER