Miller-Rabin 素性检验

费马素性检验

费马小定理提出, 也就是对于所有小于 $n$ 的正整数 $a$, 有 $a^{n - 1} \equiv 1 \pmod n$.

所以只要我们可以找到一个 $a < n$, 使得 $a^{n - 1} \not\equiv 1 \pmod n$, 那么就可以确定 $n$ 不是一个素数.

对于合数 $n$, 一定存在 $a$ 使得 $a^{n - 1} \not\equiv 1 \pmod n$. 取 $a$ 使得 $\gcd(a, b) \neq 1$, 会发现无论 $a$ 的多少次方, 都不会出现对 $\gcd(a, b)$ 取模不为 $0$ 的结果, 所以一定不会出现 $1$.

我们随机找一个正整数 $a < n$, 测试 $a^{n - 1}$ 对 $n$ 取模的结果是否为 $1$. 重复此过程一定的次数, 如果都是 $1$, 即可在一定的概率下得到 $n$ 是一个质数的结论. 否则就可以断定 $n$ 是合数. 这就是费马素性检验.

值得注意的是, 对于 $\gcd(a, n) = 1$ 的 $a$, 没有定理证明了一定存在这样的 $a$ 使得 $a^{n - 1} \equiv 1 \pmod n$. 事实上, 可以找到这样的反例, 当 $n = 561$ 时, 对于所有 $\gcd(a, n) = 1$ 的 $a$, 都有 $a^{n - 1} \equiv 1 \pmod n$. 这样的反例可以找到很多, 比如 $10^5$ 以内的反例就有: $561$, $1105$, $1729$, $2465$, $2821$, $6601$, $8911$, $10585$, $15841$, $29341$, $41041$, $46657$, $52633$, $62745$, $63973$, $75361$.

这种数叫做卡迈克尔数, 在 OEIS 中有数列A002997介绍了这种数. 费马素性检验在遇到卡迈克尔数的时候的正确率非常差, 因此一般不用于实践.

模意义下 $1$ 的平方根

对于模 $n$ 意义下 $1$ 的平方根 $x$, 满足 $x^2 \equiv 1 \pmod n$.

$\begin{aligned} x^2 &\equiv 1 \pmod n\\ x^2 - 1 &\equiv 0 \pmod n\\ (x - 1)(x + 1) &\equiv 0 \pmod n\\ kn &= (x - 1)(x + 1)\\ \end{aligned}$

如果 $n$ 是一个质数, 那么显然 $x$ 只有两种情况 $1$ 或 $n - 1$. 因为本来不含因子 $n$ 的两个正整数 $a$, $b$ 相乘后仍然不含因子 $n$, 所以模 $n$ 意义下 $x - 1$ 和 $x + 1$ 必有一个为 $0$.

但是如果 $n$ 是合数, $x$ 就可以是别的数了, 因此如果模 $n$ 意义下一个数 $x$ 的平方为 $1$, 而 $x$ 不是 $1$ 或 $-1$, 那么 $n$ 无疑是一个合数. Miller-Rabin 素性检验就是在费马素性检验的基础上多判了这种情况.

Miller-Rabin 素性检验

我们把 $n - 1$ 表示成 $2^s$ 和奇数 $d$ 的乘积, 重新审视费马小定理的式子:

$\begin{aligned} a^{n - 1} &\equiv 1 \pmod n\\ a^{2^sd} &\equiv 1 \pmod n\\ a^{2^sd} - 1 &\equiv 0 \pmod n\\ (a^{2^{s - 1}d} - 1)(a^{2^{s - 1}d} + 1) &\equiv 0 \pmod n\\ (a^d - 1)\prod_{i = 0}^{s - 1}(a^{2^id} + 1) &\equiv 0 \pmod n\\ \end{aligned}$

所以 $a^d - 1$, $a^{2^id} + 1$ 在模 $n$ 意义下只要有一个是 $0$ 即可认为 $a^{n - 1} \equiv 1 \pmod n$. 这样就不会放过费马素性检验所能检验的所有情况.

$n$ 如果是合数的话, 可能存在所有 $a^d - 1$, $a^{2^id} + 1$ 都不是 $0$, 但是满足 $a^{n - 1} \equiv 1 \pmod n$, 这是因为这些非零项相乘时得到了 $n$ 的倍数, 所以得到最终结果为 $0$. 这种情况不会被费马素性检验判为合数, 但是 Miller-Rabin 却可以判为合数.

我们思考这样判断的理由.

如果遇到 $a^{2^{i - 1}d}$ 不是 $1$ 也不是 $-1$, 但是 $a^{2^id}$ 却是 $1$, 根据前面对 $1$ 的平方根的研究, 此时 $n$ 一定是个合数.

我们把 $a^d - 1$, $a^d + 1$, $a^{2d} + 1$,…, $a^{2^{s - 1}d} + 1$ 排成一个序列.

我们发现序列中最多只会出现一个 $0$, 有 $0$ 则必定 $a^{n - 1} \equiv 1 \pmod n$. 讨论第一次出现 $0$ 是什么时候. 如果第一个 $0$ 是 $a^{2^id} + 1$, 则 $a^{2^id} \equiv n - 1 \pmod n$. 那么将它平方后一定得到 $1$, 因此之后的项都是 $1 + 1 = 2$. 如果第一个 $0$ 是 $a^d - 1$, 说明 $a^d = 1$, 因为 $1$ 的正整数次方都是 $1$, 那么从第二项开始, 就一定都是 $1 + 1 = 2$.

接下来就是序列中没有 $0$ 的情况.

讨论 $a^{n - 1}$ 是否为 $1$. 如果 $a^{n - 1}$ 为 $1$, 说明是在没有出现 $-1$ 的情况下就平方出了 $1$, 根据前面推得的结论, 不是 $1$ 或 $-1$ 的数字平方得到 $1$, 则 $n$ 是合数, 所以这时判为合数是正确的. 如果 $a^{n - 1}$ 不是 $1$, 那么根据费马素性检验, $n$ 是一个合数.

因此我们只要判断所有 $a^d - 1$, $a^{2^id} + 1$ 是否全部非 $0$, 如果不存在 $0$ 就认为 $n$ 是个合数即可. 算法实现时先求 $a^d$, 可以快速得到前两项, 然后不断将 $a^d$ 平方即可得到所有的项加 $-1$ 的结果.

算法效率和正确性

对于每个合数 $n$, 可以判出 $n$ 的 $a$ 是很多的, 所以期望只要很少次测试就可以把合数判断出来. 接下来是对英文维基百科页面的简化与复述. (这么重要的内容中文页面为什么不写?!)

根据广义黎曼猜想(我也不知道讲的是什么), 不能判出 $n$ 的 $a$ 最多有 $O((\ln n)^2)$ 个, 而这个大 $O$ 记号的常数被美国计算机科学家 Eric Bach 减少到了 $2$, 也就是说我们判断 $2((\ln n)^2)$ 个 $a$ 就可以判断出 $n$.

但是黎曼猜想的正确性现在也没有被证明, 更不用说广义黎曼猜想了, 所以为了能在有限范围内正确地快速判断质数, 我们有一些已经被验证的结论:

现在已经知道对于 $n < 4759123141$ 的情况, 我们只需要判断 $a = {2, 7, 61}$ 即可. 对于 $n < 3317044064679887385961981$, 只要判断 $a = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}$.

参考文献

• Wikipedia - 费马素性检验
• Wikipedia - Miller-Rabin primality test
• Wikipedia - 米勒-拉宾素性检验
• Shanlunjiajian - 关于素数的杂谈
• 清华大学出版社 - 信息安全数学基础
• 哈尔滨工业大学出版社 - ACM-ICPC 程序设计系列 数论及应用