Lỗi Mathematica Overflow []: Tại sao và cách bỏ qua?

Question

Tôi chưa bao giờ có lỗi tràn trong Mathematica, sau đây đã xảy ra.

tôi giới thiệu-ed nguyên tắc RSA-mã hóa như sau:

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 

Không có vấn đề sofar.

Sau đó, tôi đã thay đổi số nguyên tố thành kích thước thực tế hơn nhưng vẫn rất vừa phải.

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

Câu hỏi: Tôi đã trải qua giới hạn của Mathematica chưa? Tôi đã sử dụng một cách tiếp cận không chính xác? Điều gì là by-pass, nếu có?

Answer 1

Hãy thử sử dụng PowerMod trong hoạt động decyphering:

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

Vâng, bạn đã trải qua những giới hạn của Mathematica. Số lượng tối đa có thể được biểu diễn trên một hệ thống trong một phiên bản cụ thể của Mathematica được hiển thị bởi $MaxNumber. Trong ví dụ thứ hai của bạn, d=18158086021982021938023 và do đó 27136050989627^d là cách lớn hơn $MaxNumber.

Bạn có thể sử dụng PowerMod trong bước thứ hai quá như bạn đã làm cho d, mà sẽ tính toán a^b mod n hiệu quả hơn Mod. Với decipher2[x_List] := FromCharacterCode[Map[PowerMod[#, d, n] &, x]], bạn nhận được:

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

Yep, như anh chàng khác đã trả lời bạn đã tốt và thật sự đạt đến $ MAXNUMBER Mathematica có thể xử lý.

Có đường vòng sẽ tìm mod cho nhiều số lớn lớn hơn $ MaxNumber.

Thay vì gán trực tiếp số lớn vào Mathematica, chẳng hạn như 163840000000^18158086021982021938023, điều này cực kỳ lớn, hãy sử dụng số học mô-đun để tiết kiệm Mathematica sự cố phải tính toán số lượng lớn như vậy.

Bạn sẽ có thể phát triển Mã Mathematica cho điều này, tôi chưa biết cách thực hiện việc này. Nhưng bạn có thể làm điều đó bằng tay, bằng cách tìm: 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]

mà cho câu trả lời chính xác bạn đang tìm kiếm, mà không vượt quá $ MAXNUMBER