2^100 是 1267650600228229401496703205376,三十一位,螢幕印成 1.2676506002282⋅10+30。在同一個視窗裡問 2^100 mod 7,答案卻是 0。問 2^4 mod 7,答案是 2——而這才是對的那一個:2^3 = 8 ≡ 1 (mod 7),所以 2^99 ≡ 1 且 2^100 ≡ 2;等價地說,2^6 ≡ 1 而 100 mod 6 = 4,整個題目就歸約成 2^4 mod 7。
冪本身沒算錯,錯的是餘數。一個雙精度數存 53 位元,2^100/7 最近的可表示值偏差在 10^13 這個量級,而按 a − 7·floor(a/7) 算出的餘數就繼承了一個遠大於模數的誤差。正確的做法絕不讓數長起來:先化簡再乘方,這正是每個密碼函式庫裡的模冪運算在做的事,也是 RSA 能在一台只存 53 位元的硬體上處理上千位數字的原因。同一層天花板也讓 2^53 成了最後一個精確的整數計數器。
答案
0
口徑說明
工作台上的 2^100 mod 7——機器給的答案,不是算術給的答案。第二個連結是 2^6 mod 7 = 1,即週期;第三個是化簡後的問題 2^4 mod 7 = 2,那才是真正的值。
出處
2^100 = 1267650600228229401496703205376 is exact in binary floating point, being a power of two, but the quotient by 7 has thirty significant digits and IEEE-754 binary64 carries only about sixteen, so a mod implemented as a − b·floor(a/b) returns a remainder taken from the rounded quotient
在計算機裡做這道題
下面的連結直接開啟對應的計算機,並把這道題的數字填進螢幕——答案就是上面那一行,可以自己核對。
題目詳情頁 · 正文末尾、頁底說明之前
320×100 px 的廣告位
728×90 px 的廣告位