Ошибка Mathematica Overflow []: почему и как обойти?

Question

У меня никогда не было ошибки переполнения в Mathematica, произошло следующее:

Я продемонстрировал принцип RSA-шифрования следующим образом:

 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

Нет проблем, софар.

Затем я изменил простые числа на более реалистичный, но все же очень умеренный размер.

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

Вопрос: Я просто прошел через пределы Mathematica?Я использовал неправильный подход?Что такое обходной путь, если таковой имеется?

Answer 1

Попробуйте использовать PowerMod в операции дешифрования:

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

Да, вы прошли через пределы Mathematica. Максимальное число, которое может быть представлено в системе в конкретной версии Mathematica, обозначено $MaxNumber. Во втором примере d=18158086021982021938023 и, следовательно, 27136050989627^d намного больше, чем $MaxNumber.

Вы можете использовать PowerMod на втором шаге так же, как и для d, который будет вычислять a^b mod n более эффективно, чем Mod. С decipher2[x_List] := FromCharacterCode[Map[PowerMod[#, d, n] &, x]] вы получите:

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

Да, как ответил другой парень, вы хорошо и верно достигли $ MaxNumber, с которым Mathematica может справиться.

Существует обходной путь, который найдет мод для многих больших чисел, больших, чем $ MaxNumber.

Вместо того, чтобы вписывать большие числа непосредственно в Mathematica, например, 163840000000 ^ 18158086021982021938023, который является огромным, используйте модульную арифметику, чтобы избавить Mathematica от необходимости вычислять такое большое число.

Вы должны быть в состоянии развитьКод Mathematica для этого я пока не знаю, как это сделать.Но вы можете сделать это вручную, найдя: 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]

, что дает правильный ответ, который вы ищете, не превышая $ MaxNumber