模运算

先看一个麻烦

现在是 10 点，过 5 个小时是几点？

3 点。你不用想就知道。但注意你刚做了什么：你算出 15，然后把 12 减掉了。

再来。现在是 10 点，过 100 个小时是几点？

这次得停一下。110 减 12 是 98，再减……不对，这么减下去太蠢。100 里有 8 个 12（96），余 4，所以 10 + 4 = 14，再减 12 得 2 点。

你刚才做的事有个名字。而且它不只是钟表的小把戏——它是密码学能存在的原因。

最自然的想法是：先老老实实算，最后取余数。

算 2¹⁰⁰ 除以 7 的余数？那就先算 2¹⁰⁰ 吧。这个数有 31 位十进制数字，勉强还行。

那 2^(1000000) 除以 7 呢？这个数有三十万位。你的机器算得出来，但已经开始难受了。

密码学里的指数是 2048 位的数。那个中间结果的位数比宇宙里的原子数还多。先算完再取余这条路是死的。

救命的性质是这个：取余可以提前做，随时做，做多少次都不影响结果。

$(a \times b) \bmod n = ((a \bmod n) \times (b \bmod n)) \bmod n$

加法同理。也就是说你永远不需要让数字长大——每一步乘完立刻取余，数字就被永久关在 0 到 n−1 这个笼子里。

算 2¹⁰⁰ mod 7： 2¹ = 2，2² = 4，2³ = 8 → 1（mod 7）。

到这儿就够了。2³ ≡ 1，所以每三次乘方回到原点。100 = 3 × 33 + 1，于是 2¹⁰⁰ ≡ 2¹ = 2（mod 7）。

一个三十万位的数，用一行心算解决了。这不是技巧，是模运算的结构本身——余数构成一个有限的、封闭的算术系统。

AKS 论文开篇复述费马小定理时，用的正是这套记号：

for any prime number p, and any number a not divisible by p, ap−1 = 1 (mod p)

对任意素数 p 和任意不被 p 整除的数 a，都有 a^(p−1) ≡ 1 (mod p)。

留意作者紧接着的态度——他们没说这给了个素数判定法，而说它”几乎”给了一个：

A property that almost gives an efficient test is Fermat’s Little Theorem

因为反过来不成立。有些合数也满足这个式子，卡迈克尔数甚至对所有 a 都满足。这条”差一点就成”的缝隙，是后面二十多年素数判定研究的起点。

写代码的人容易把 % 当成一个运算符就完事了。数学上它是别的东西。

a mod n 是一个运算，给你一个 0 到 n−1 的数。 a ≡ b (mod n) 是一个关系，说的是 a 和 b 除以 n 余数相同。

这个区别有实际后果。当你说”在 mod 7 的世界里”，你不是在算余数，而是把所有整数按余数分成 7 堆，然后宣布同一堆里的数就是同一个数。7 和 14 和 −7 在这里是同一个对象。

一旦这样看，“负数取模是多少”这类困惑就消失了：−1 ≡ 6 (mod 7)，因为它们在同一堆。而编程语言里 -1 % 7 给 −1 还是 6，取决于语言设计者选了哪个代表元，跟数学无关。

模运算下除法不总是能做。在 mod 6 里，2 没有倒数——没有任何 x 满足 2x ≡ 1 (mod 6)。只有当 n 是素数时，1 到 n−1 每个数才都有倒数，此时这个系统构成一个域。

这正是密码学偏爱素数模的原因，也是为什么”这个数是不是素数”从一个纯数论问题变成了工程刚需。