米勒–拉宾素性检验是一种素性检验算法,用于判定一个整数是合数还是可能素数。它对一系列模幂应用素数必须满足的条件。只要有一个条件不成立,就能证明输入是合数;但仅仅通过检验,并不能证明它是素数。对于任意固定的奇合数输入,独立、均匀随机选取一个检验底数,未能识别其合数性的概率不超过 。使用独立的随机底数重复检验,可以使这一错误概率的上界呈指数下降。
该检验速度快、实现简单,而且能有效处理极大的整数,因此广泛用于计算数论和密码学中的素数生成。
数学基础
设 是奇整数。将其写为
其中 为奇数,且 。选取整数底数 ,满足 ,考虑模算术中的序列
从第二项起,每一项都是将前一项平方后对 取模得到的。
如果 是素数,由费马小定理可得
此外,在模素数的意义下, 的平方根只有 和 。这是因为这些剩余类构成一个有限域,在域中,
意味着 或 。
因此,如果 是素数,则要么
要么
这两种情形构成了以 为底的强可能素数条件。如果两者都不成立, 就必定是合数。
一种等价的理解方式是:从序列的最后一项出发,沿着平方链向前回溯;对于素数,最后一项必定为 。除非首项已经是 ,否则平方链第一次得到 时,必定是对 求平方的结果。如果对其他剩余类求平方得到 ,就出现了模素数时不可能发生的情况。
算法
小于 的输入不是素数。整数 和 是素数,大于它们的偶数都是合数。对于其余的奇数输入,检验步骤如下。
MillerRabin(n, k):
如果 n < 2:
返回 非素数
如果 n = 2 或 n = 3:
返回 素数
如果 n 是偶数:
返回 合数
将 n - 1 写成 2^s * d,其中 d 为奇数
重复 k 次:
从 {2, ..., n - 2} 中均匀随机选取 a
x = a^d mod n
如果 x = 1 或 x = n - 1:
进入下一轮
passed = 假
重复 s - 1 次:
x = x^2 mod n
如果 x = n - 1:
passed = 真
跳出循环
如果 x = 1:
返回 合数
如果 passed 为假:
返回 合数
返回 可能素数
这里, 是指定检验轮数的正整数。初始幂通过模幂运算计算,而不是先构造出巨大的整数 。
也可以选择先计算最大公约数,从而立即发现一个因数:如果 ,那么 就是合数。通常的算法并不需要这一步检查也能保证正确性。
在筛选大量候选数时,先用少量素数进行整除性检验,再运行米勒–拉宾检验,往往能减少总计算量。
见证底数、说谎底数与强伪素数
使检验拒绝 的底数称为合数性的强见证底数,也简称为米勒–拉宾见证底数。如果 是合数,却通过了某个底数的检验,那么这个底数就称为强说谎底数,而 则称为以该底数为底的强伪素数。
这些术语描述的是一个数与一个底数之间的关系。一个合数可能通过某个底数的检验,却无法通过另一个底数的检验。
示例:识别费马伪素数
考虑
以 为底时,
下一次平方得到
初始值既不是 ,也不是 ,而平方步骤在尚未出现 的情况下就得到了 。因此,米勒–拉宾检验证明了 是合数。
然而,
所以 能通过较简单的以 为底的费马检验。米勒–拉宾检验从中间的幂中提取了更多信息。
的这个非平凡平方根还揭示了因数:
有时可以这样找出因数,但米勒–拉宾见证底数并不一定能直接给出因数。
示例:通过检验的合数
合数
能通过以 为底的检验。这里 ,并且
因此,仅通过一轮检验并不能确定一个数是素数。
错误概率保证及其含义
对于每个奇合数 ,在底数 中,强说谎底数的数量至多为 。更小的奇合数 也很容易处理,而采用标准抽样区间 时,就能得到通常所说的每轮错误概率至多为 的上界。
对于一个固定的合数输入,以及 个独立、均匀抽样得到的底数,
例如,进行 轮检验时,最坏情况下的上界为
这一保证是单侧的:
- 假设算术运算和实现正确,素数输入总能通过检验。
- 合数输入可能通过检验,但在上述抽样假设下,通过检验的概率有明确的上界。
用随机算法的术语来说,米勒–拉宾检验是一种具有单侧错误的蒙特卡洛方法。
这一条件概率的条件方向很重要。上述上界并不自动等于被接受的数是合数的概率:
还取决于候选数的选取方式,以及其中素数原本所占的比例。它与一个固定合数通过检验的概率是不同的量。
重复检验的概率上界依赖于底数选择的独立性和均匀性。重复使用同一个底数不会提供额外的数学保证;任意选取一些可预测的底数,也不会仅仅因为数量达到 个,就获得 的保证。
确定性版本
虽然通用的米勒–拉宾检验是随机算法,但在若干情形下,可以将其变为确定性算法。
有界输入范围
对于指定的有限整数范围,有一些经过证明的底数集合,足以区分该范围内的所有素数与合数。例如,检验以下十二个素数底数
并按通常方式处理较小的输入,就足以检验所有 的输入。
使用固定底数列表的实现必须正确处理普通抽样区间之外的底数,例如先将其对 取模,并妥善处理平凡的剩余类。所用的有界范围定理也必须与实际输入范围相符。一个足以处理 64 位整数的底数集合,并不因此就足以处理任意精度整数。
有条件的确定性检验
在某种适当形式的广义黎曼猜想成立的前提下,米勒最初的方法给出了一个确定性多项式时间检验。在这一假设下,每个奇合数都有一个见证底数,其大小不超过 的某个常数倍,因此只需检查不超过这一上界的所有底数。
如果不采用该假设,目前尚不知道同样的小底数上界是否普遍成立。虽然存在无条件的确定性多项式时间素性检验算法,但它们使用的是不同的方法。
计算成本
设 为 的二进制位数。二进制模幂运算需要 次模乘,随后的平方链也至多需要 次模乘。
因此,采用传统的整数算术算法时,一轮检验需要
次位运算,而 轮检验需要
这些表达式使用了大O记号。更快的乘法和模约减方法可以改善位复杂度。更一般地,如果两个 位数的模乘成本为 ,则总成本约为 。
许多合数候选值在第一轮就会被排除,因此无需承担全部 轮的计算成本。素数输入会通过每一轮,因此需要完成规定的全部计算。
历史与实际作用
加里·L. 米勒于 1976 年发表了依赖假设的确定性理论基础。迈克尔·O. 拉宾于 1980 年发表了随机化形式,其依据是:对每个奇合数,都有很大一部分底数能够揭示其合数性。
米勒–拉宾检验后来成为生成大型可能素数的标准工具。典型流程是先生成所需位数的候选数,排除能被小素数整除的数,再对剩余候选数进行多轮米勒–拉宾检验。素数定理解释了为什么在大整数中,素数的出现频率仍足以使反复生成候选数的方法切实可行。
该检验有若干重要局限:
- 可能为素数不等于已经证明是素数。 通过随机轮次的检验只能给出量化的错误概率上界,并不构成一般意义上的素性数学证明。
- 算术运算必须精确。 即使数学算法本身正确,固定位宽乘法中的溢出也可能导致模运算出错。
- 底数选择过程是保证的一部分。 对于有偏或相互依赖的选择方式,需要另行分析。
- 检测见证底数并不等于通用的因数分解。 被拒绝的候选数已知是合数,但其因数可能仍然未知。
- 固定底数的保证有范围限制。 对经过证明的有限底数集合,不能在没有依据的情况下将其适用范围扩展到已确立的范围之外。
当需要可验证的素性证书时,可以先用米勒–拉宾检验进行初步筛选,再使用独立的素性证明程序。