Miller-Rabin 测试告诉了我们什么？

weilycoder · 2026-02-10 12:19:26 · 算法·理论

基本流程

简单来说，Miller-Rabin 测试是一种（非确定）素性测试算法．对于给定的 n，算法的具体流程如下：

• 在 (1, n-1) \cap \mathbb{N} 中随机选择一个数 a（假定 n 较大，不考虑边界情况）；
• 将 n 写成 s \cdot 2^t 的形式，其中 2 \nmid s，t\in\mathbb{N}；
• 计算 a_0 = a^{s} \bmod n，若 a_0 = 1，返回 \mathtt{false}；
• 依次计算序列 \langle a_0, a_1, a_2, \ldots, a_t \rangle，其中 a_i = 2 \cdot a_{i-1} \bmod n（i \geqslant 1）；
• 若 a_t \neq 1，返回 \mathtt{true}；
• 若存在 i \geqslant 1 使得 a_i = 1 且 a_{i-1} \notin \{-1, 1\}，返回 \mathtt{true}；
• 返回 \mathtt{false}．

如果算法返回 \mathtt{true}，则称 a 是 n 为合数的一个证人（witness），此时 n 是合数．

若算法返回 \mathtt{false}，n 仍可能是合数，此时称 n 是基于 a 的强伪素数（strong pseudoprime），a 称为 n 的强骗子（strong liar）．

思想和错误率

Miller-Rabin 测试的思想基于以下两个定理：

1. 费马小定理

   a^{p-1} \equiv 1 \pmod{p}

2. 二次探测定理

   在模 p 意义下，满足 a^2 \equiv 1 \pmod{p} 的 a 只有 \pm 1．

这里 p 均表示质数．

因此，若算法返回 \mathtt{true}，则 n 一定是合数．

并且可以证明[^1]，当 n 是合数时，强骗子的数量至多为 \frac{\varphi(n)}{4}，且存在 n 使得该上界达到．

换言之，在 n 为合数的情况下，单次 Miller-Rabin 测试出错的概率不超过 \frac{1}{4}．

[^1]: 具体参见 OI-wiki 相关章节及其引用．

贝叶斯概率分析

然而，这并不意味着进行 k 轮 Miller-Rabin 测试后，n 为合数的概率就衰减到 4^{-k}．

考虑贝叶斯公式：

根据相关结论，\Pr\left(\mathrm{MR}_k \mid \neg P\right) \leqslant 4^{-k}，因此

这个概率与被测试数为质数的先验概率有关，遗憾的是后者难以把控（例如攻击者可能只发送合数）．

假设 \Pr\left(P\right) = \frac{1}{\ln N}（即假定均匀随机选取），则 k 轮 Miller-Rabin 测试后，待测数不是质数（假阳性）的概率小于 \frac{\ln N - 1}{4^k}，这意味着需要进行大约 \log_{4}\ln N 次素性测试以抵消质数分布带来的较低先验概率．

不过，如果待测数确实均匀随机选取，先验概率的影响会比以上估计更小，因为均匀随机下合数的假阳性概率低于 \frac{1}{4}．

:::info[AI 使用说明]{open} 使用 Deepseek 调整排版． :::