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
在计算器里做这道题
下面的链接直接打开对应的计算器,并把这道题的数字填进屏幕——答案就是上面那一行,可以自己核对。