Miller Rabin概率素性测试与合数证据解析

随机算法能生效，靠的可不是什么运气玄学，而是候选空间里堆满了可用的证据。只要证据足够密集，随机抽样就不再是瞎蒙，而是一种成本极低的搜索策略。

想象一下：给定某个输入 x，如果额外附上一段信息 w，就能比直接求解更高效地验证某个结论。在计算复杂性里，这种辅助信息通常被称为 witness，可以理解为“证人”或“证据”。算法不需要知道 witness 藏在哪里，也没法直接构造它们；它只需要具备一个能力——高效检查某个候选者是不是合格的 witness。只要 witness 在候选集合里足够多，随手抽一个，命中的概率就不低。

素数测试就是这个思路的经典代言人。我们要判断一个正整数 n 是素数还是合数。直接分解 n 目前没有已知的多项式时间算法，但证明“n 是合数”有时候却容易得多——只要找到一条合适的证据。

素数测试问题

给定整数 n，最直接的素数测试是试除法：从 2 一直试到 √n，只要发现某个 i 整除 n，就知道 n 是合数。

is_prime(n): i = 2 while i <= sqrt(n): if n mod i == 0: return false i = i + 1 return true

光从数值上看，这个算法的复杂度是 O(√n)，似乎还能接受。但在这类问题里，输入的规模通常不是数字 n 本身，而是 n 的位数。设输入长度为 l，那么大约有 l = log n。试除到 √n 等价于试到 2^{l/2}，妥妥的指数时间算法。

所以，高效的素数测试真正要解决的是：能否在 log n 的多项式时间内完成？这就要求我们不能逐个检查可能的因子，而是去寻找更“便宜”的证据。

什么样的 witness 才有用

谁能证明“n 是合数”？一个最自然的 witness 是 n 的非平凡因子。只要存在 a 满足 1 < a < n 且 a | n，那么 a 就可以直接证明 n 是合数。检查它也很快，算一下 n mod a 就行了。

问题在于，因子作为 witness 太稀疏了。假设 n = p × q，其中 p 和 q 是两个大素数。候选集合可以取 2, …, n-1，大小接近 n，但真正能整除 n 的候选者可能只有那么几个。随机抽一个数，命中因子的概率低得可怜。

这说明 witness 的定义不能只满足“可验证”，还得满足“数量多”。一个适合随机算法的 witness 定义，通常要满足三个条件：它能高效证明目标结论；任意候选者是否为 witness 可以高效检查；在候选集合中，witness 的比例不能太低，最好有常数级下界。

换句话说，设候选集合为 C，witness 集合为 W ⊆ C。我们希望存在常数 α > 0，使得 |W| / |C| ≥ α。这样随机抽取一个候选者，命中 witness 的概率至少是 α。

随机算法并不害怕不知道 witness 在哪里；它真正怕的是 witness 太少。只要证据足够多，随机性就能把“寻找证据”的成本降下来。

Fermat 测试：从素数的必要条件出发

好在有这么一个数学定理能帮上忙。Fermat 小定理给出了一个更好的方向。它的内容是：若 n 是素数，且 a 不被 n 整除，则有

a^{n-1} ≡ 1 (mod n)

这提供了一个反向证据：如果我们找到某个 a，使得 a^{n-1} ≠ 1 (mod n)，那么 n 一定不是素数。这样的 a 就可以作为 n 为合数的 witness。

于是可以写出一个简单的测试：

fermat_test(n, a): if pow_mod(a, n-1, n) != 1: return composite else: return probably_prime

这里的 pow_mod 不是先算出巨大的 a^{n-1} 再取模，而是在每一步乘法后取模——也就是快速模幂。因为指数 n-1 有 O(log n) 位，可以在 O(log n) 次模乘内完成，这已经是输入长度的多项式时间。

实际实现中，通常还会先算一下 gcd(a, n)。如果 1 < gcd(a, n) < n，那我们已经找到了 n 的一个非平凡因子，可以立即判定 n 是合数。

如果固定取 a=2，可以得到一个非常便宜的测试：

if pow_mod(2, n-1, n) == 1: return probably_prime else: return composite

如果返回 composite，结果是确定的；如果返回 probably_prime，则不一定正确。因为存在一些合数 n 也满足 2^{n-1} ≡ 1 mod n，这类数被称为以 2 为底的 Fermat 伪素数。

这时随机选择底数 a 可以减少对单个底数的依赖：

a = random integer in [2, n-2] if pow_mod(a, n-1, n) == 1: return probably_prime else: return composite

但仍然不够理想。有些合数会对大量底数通过 Fermat 条件。问题不是模幂计算不够快，而是 witness 的定义还不够强。

Fermat 测试只看终点：a^{n-1} 是否等于 1。如果只看终点，有些合数确实能伪装得很好。Miller-Rabin 测试的改进之处就在于，它不只看终点，还检查通向这个终点的平方链是否像素数模数下那样“合法”。

Miller-Rabin：更强的合数证人

Miller-Rabin 测试对 Fermat 条件做了加强，将得到 a^{n-1} mod n 的过程分解来看。

对于奇数 n ≥ 5，把 n-1 提出 2 的因子，写成

n-1 = 2^t × u

其中 u 是奇数。然后随机选择一个候选底数 a，先计算 x0 = a^u mod n，然后不断平方：

x_i = x_{i-1}^2 mod n

不难推出，最终的 x_t = a^{n-1} mod n。最终结果和 Fermat 测试的判定是一致的，但这里增加了对中间结果的检查。如果 n 是素数，那么这条平方链必须满足一些非常受限的结构。Miller-Rabin 的 witness 检查正是利用了这些结构。

witness(a, n): write n-1 = 2^t * u, where u is odd x = pow_mod(a, u, n) repeat t times: y = x * x mod n if y == 1 and x != 1 and x != n-1: return true x = y if x != 1: return true return false

witness(a, n) 返回 true 表示 a 成功证明了 n 是合数。

这里有两类失败模式。第一类是 Fermat 条件本身失败：最终得到的 a^{n-1} mod n 不是 1，那么 n 必然是合数。第二类更微妙：在平方链中间出现了 1 的非平凡平方根。

这是因为质数有一个特殊性质：对于素数模数，1 的平方根只能是 ±1（也就是 1 和 n-1）。出现其他平方根，说明模数一定不是素数。这一点可以从 (x-1)(x+1) ≡ 0 (mod n) 看出来：若 n 是素数，乘积为 0 意味着至少一个因子为 0，所以 x ≡ 1 或 x ≡ -1。只有合数模数下才可能出现更复杂的零因子现象。

因此，如果在迭代过程中，某一步有 y ≡ 1 mod n，而对应的 x 既不是 1 也不是 n-1，那么 n 一定不是质数。

错误概率指数下降

这样一来，Miller-Rabin 的完整算法很短：

miller_rabin(n, s): if n < 2: return composite if n == 2 or n == 3: return prime if n mod 2 == 0: return composite repeat s times: a = random integer in [2, n-2] if witness(a, n): return composite return probably_prime

这个算法有单侧错误。如果它返回 composite，一定正确，因为已经找到了合数 witness。如果它返回 probably_prime，表示在 s 次随机尝试中都没有找到 witness。

更准确地说，若 n 是素数，任何合法底数都不会让 Miller-Rabin 返回 composite。错误只可能发生在另一侧：n 实际上是合数，但随机选择的底数都没有暴露它的合数性。

对于任意奇合数 n，可以证明，至少有四分之一的底数会让合数通过 Miller-Rabin 测试。也就是说，至少四分之三的候选底数可以作为合数 witness。因此，如果 n 实际上是合数，一次随机测试没有命中 witness 的概率至多为 1/4。

独立重复 s 次时，全部失败的概率至多是

P(error) ≤ (1/4)^s = 4^{-s}

这就是 witnesses 的力量。算法不需要知道 witness 分布在哪里，也不需要显式构造它们；只要 witness 在候选集合里足够密集，随机抽样就足以给出很强的概率保证。

实际使用中，s = 40 已经让错误概率小到可以忽略。如果应用场景需要更强保证，可以继续增加 s，代价只是线性增加测试轮数。

常用的底数选取和已知伪素数

在实际应用中，当需要完全确定地判断一个不超过某个上限的整数是否为素数时，可以放弃随机抽样，转而使用一组固定且经过验证的底数。此时 Miller-Rabin 测试退化为确定性算法，因为对于该范围内的所有合数，至少其中一个底数能充当 witness。

常见确定性底数集合

已知的强伪素数（Strong Pseudoprime）

即便使用了 Miller-Rabin，某些合数仍能针对一组特定底数“伪装”成素数。这些数被称为强伪素数。

• 以 2 为底的强伪素数：最小的是 2,047 = 23 × 89。也就是说，Miller-Rabin 测试若只用 a=2，会把 2047 判为素数。
• 以 2 和 3 为底的强伪素数：最小的是 1,373,653 = 829 × 1,657。
• 同时以 2、3、5、7 为底的强伪素数：已知最小的是 3,215,031,751 = 151 × 751 × 28,351。

总的来说，Miller-Rabin 之所以能从“概率算法”走向“工程上可信任的实用工具”，正是基于一个根本事实：合数的 witness 在底数空间中占据压倒性多数（至少 75%）。只需少量随机抽样，就能以指数速度衰减的误差概率获得正确判定。

这些例子也说明了为何不能依赖少数几个固定底数做广泛范围的素数测试。对于超出上述表格范围的整数，仍然应该使用随机底数，保证高概率正确。

确定性素数测试

长期以来，一个自然的问题是：这些 witness 是否只是“随机上很多”，还是存在某种可被确定性利用的结构？2002 年，AKS 素数测试给出了确定性多项式时间算法，证明素数判定确实属于 P。这在理论上非常重要，因为它不依赖随机抽样，也不再输出 probably_prime，而是确实有多项式时间准确判定是否是素数的方法。

不过，理论复杂度和工程表现是两回事。AKS 的历史意义不等于它在常规应用中优于 Miller-Rabin。实际系统里，Miller-Rabin 仍然常用，因为它实现简单、速度快，并且错误概率可以通过重复测试降到极低。对于许多固定字长整数，还可以选择一组已知底数，使 Miller-Rabin 在该范围内变成确定性测试。

同时，“Abundance of Witnesses”给出的不是某个特定算法技巧，而是一种设计算法的角度：如果直接求解困难，就寻找一种容易验证且大量存在的证据。素数测试里，因子是证据，但太少；Fermat witness 更便宜，但不够强；Miller-Rabin witness 把“证据密度”和“验证效率”平衡到了一个适合随机算法的位置。随机性在这里不是替代证明，而是用来快速找到证明。