素数从哪来：费马检验、Carmichael 数与 Miller–Rabin

全文分三层：

1. 通俗理解：为什么不分解也能判断素数，"随机抽查"的思路
2. 实际用处：RSA 密钥生成、OpenSSL，以及素数生成出错的事故
3. 数学原理：费马检验、Carmichael 数、Miller–Rabin 的正确性，附 $561$ 的手算例子

第一层：通俗理解

1.1 判断素数比分解容易得多

"$N$ 是不是素数"和"$N$ 等于哪两个数相乘"听起来像同一个问题，其实难度天差地别：

• 判断一个 1000 位的数是否为素数：笔记本电脑不到一秒；
• 分解一个 600 位（2048 比特）的 RSA 模数：目前全人类的计算机加起来也做不到。

神奇之处在于，素性检验可以不找出任何因子就断定一个数是合数。就像验钞机不用知道假钞是谁印的，只要发现某个特征不对就行。

1.2 素数够多吗

素数定理说，$N$ 附近大约每 $\ln N$ 个数里有一个素数。对 1024 位的数，$\ln 2^{1024} \approx 710$；只挑奇数的话，平均试约 355 个就能碰到一个素数。每次测试都很快，所以生成素数并不慢。

1.3 "抽查"的思路

素数一定满足某些性质（比如费马小定理）。我们随机挑一些底数 $a$ 去检查：

• 只要有一次不满足，肯定是合数；
• 每次都满足，很可能是素数。

关键是设计一种检查，让合数"蒙混过关"的概率足够低。Miller–Rabin 每轮至多 $1/4$ 的概率被骗，做 40 轮，被骗概率不超过 $4^{-40} = 2^{-80}$，比硬件出错的概率还低。

第二层：实际用处

• RSA 密钥生成：OpenSSL、BoringSSL、各种硬件安全模块都用"小素数试除 + Miller–Rabin"的组合。先用前几百个小素数做试除，可以很快排除大部分候选数。
• Diffie–Hellman 参数：生成"安全素数" $p = 2q + 1$，需要 $p$ 和 $q$ 同时是素数。
• 标准：美国 FIPS 186-5 规定了密钥生成时 Miller–Rabin 的轮数，有时还会加上 Lucas 检验（两者组合叫 Baillie–PSW，至今没找到能骗过它的合数）。

第三层：数学原理

3.1 费马检验

费马小定理：若 $p$ 是素数，$\gcd(a, p) = 1$，则 $a^{p-1} \equiv 1 \pmod p$。（这是 $\mathbb{Z}_p^\times$ 阶为 $p-1$ 时的拉格朗日定理。）

检验：随机选 $a$，算 $a^{N-1} \bmod N$。不等于 $1$，$N$ 一定是合数。

大多数合数都过不了这一关。例如 $N = 15$，$2^{14} = 16384 \equiv 4 \pmod{15}$，立刻露馅。

3.2 Carmichael 数

有一类合数，对所有与它互素的 $a$ 都满足 $a^{N-1} \equiv 1$，叫 Carmichael 数。

Korselt 判据：合数 $N$ 是 Carmichael 数，当且仅当 $N$ 无平方因子，并且对每个素因子 $p \mid N$ 都有 $(p - 1) \mid (N - 1)$。

最小的例子 $561 = 3 \times 11 \times 17$：$560$ 能被 $2$、$10$、$16$ 整除。由中国剩余定理，$a^{560}$ 在模 $3$、$11$、$17$ 下都是 $1$，所以模 $561$ 也是 $1$。

1994 年 Alford、Granville、Pomerance 证明了 Carmichael 数有无穷多个。所以单靠费马检验是不行的。

3.3 关键引理：模素数时 $1$ 只有两个平方根

若 $p$ 是奇素数，$x^2 \equiv 1 \pmod p$，则 $p \mid (x-1)(x+1)$。因为 $\mathbb{Z}_p$ 是域（没有零因子），只能 $x \equiv 1$ 或 $x \equiv -1$。

反过来，如果找到 $x \not\equiv \pm 1$ 但 $x^2 \equiv 1 \pmod N$，那么 $\mathbb{Z}_N$ 有零因子，$N$ 一定是合数（而且 $\gcd(x - 1, N)$ 就是一个非平凡因子）。

3.4 Miller–Rabin

把 $N - 1$ 写成 $2^s \cdot d$，$d$ 为奇数。随机选 $a$，看这串数：

$$a^d,\ a^{2d},\ a^{4d},\ \dots,\ a^{2^s d} = a^{N-1} \pmod N.$$

每一项是前一项的平方。如果 $N$ 是素数，由费马小定理最后一项是 $1$；再由 3.3 的引理，倒着往回开平方，第一次离开 $1$ 时必须是 $-1$。所以素数一定满足：

要么 $a^d \equiv 1$，要么这串数里某一项等于 $-1$。

不满足就判定合数。Rabin 证明了：对合数 $N$，至多 $1/4$ 的底数 $a$ 能骗过这个检验。

3.5 手算例子：揭穿 $561$

3.6 确定性算法

2002 年，Agrawal、Kayal、Saxena 给出了 AKS 算法，第一次证明了素性检验可以在确定性多项式时间内完成（论文题目就叫 PRIMES is in P）。不过它比 Miller–Rabin 慢得多，实际中仍用概率算法。

总结