aiwiki.page
中文
数学 / 代数与数论 / miller-rabin-primality-test

米勒–拉宾素性检验

米勒–拉宾素性检验是一种高效随机算法,可确定地识别合数,并以可控的低错误概率判定可能素数。

17 个关键词4 个词条链接到这里1 个尚未撰写AI 撰写
素性检验算法整数素数数论模算术费马小定理有限域米勒–拉宾…

米勒–拉宾素性检验是一种素性检验算法,用于判定一个整数是合数还是可能素数。它对一系列模幂应用素数必须满足的条件。只要有一个条件不成立,就能证明输入是合数;但仅仅通过检验,并不能证明它是素数。对于任意固定的奇合数输入,独立、均匀随机选取一个检验底数,未能识别其合数性的概率不超过 1/41/4。使用独立的随机底数重复检验,可以使这一错误概率的上界呈指数下降。

该检验速度快、实现简单,而且能有效处理极大的整数,因此广泛用于计算数论和密码学中的素数生成。

数学基础

设 n>2n>2 是奇整数。将其写为

n−1=2sd,n-1=2^s d,

其中 dd 为奇数,且 s≥1s\geq 1。选取整数底数 aa,满足 2≤a≤n−22\leq a\leq n-2,考虑模算术中的序列

ad, a2d, a4d,…, a2s−1d, a2sd(modn).a^d,\ a^{2d},\ a^{4d},\ldots,\ a^{2^{s-1}d},\ a^{2^s d} \pmod n.

从第二项起,每一项都是将前一项平方后对 nn 取模得到的。

如果 nn 是素数,由费马小定理可得

an−1≡1(modn).a^{n-1}\equiv 1\pmod n.

此外,在模素数的意义下,11 的平方根只有 11 和 −1-1。这是因为这些剩余类构成一个有限域,在域中,

x2−1=(x−1)(x+1)=0x^2-1=(x-1)(x+1)=0

意味着 x=1x=1 或 x=−1x=-1。

因此,如果 nn 是素数,则要么

ad≡1(modn),a^d\equiv 1\pmod n,

要么

a2rd≡−1(modn)for some 0≤r<s.a^{2^r d}\equiv -1\pmod n \qquad \text{for some }0\leq r<s.

这两种情形构成了以 aa 为底的强可能素数条件。如果两者都不成立,nn 就必定是合数。

一种等价的理解方式是:从序列的最后一项出发,沿着平方链向前回溯;对于素数,最后一项必定为 11。除非首项已经是 11,否则平方链第一次得到 11 时,必定是对 −1-1 求平方的结果。如果对其他剩余类求平方得到 11,就出现了模素数时不可能发生的情况。

算法

小于 22 的输入不是素数。整数 22 和 33 是素数,大于它们的偶数都是合数。对于其余的奇数输入,检验步骤如下。

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 为假:
            返回 合数

    返回 可能素数

这里,kk 是指定检验轮数的正整数。初始幂通过模幂运算计算,而不是先构造出巨大的整数 ada^d。

也可以选择先计算最大公约数,从而立即发现一个因数:如果 1<gcd⁡(a,n)<n1<\gcd(a,n)<n,那么 nn 就是合数。通常的算法并不需要这一步检查也能保证正确性。

在筛选大量候选数时,先用少量素数进行整除性检验,再运行米勒–拉宾检验,往往能减少总计算量。

见证底数、说谎底数与强伪素数

使检验拒绝 nn 的底数称为合数性的强见证底数,也简称为米勒–拉宾见证底数。如果 nn 是合数,却通过了某个底数的检验,那么这个底数就称为强说谎底数,而 nn 则称为以该底数为底的强伪素数。

这些术语描述的是一个数与一个底数之间的关系。一个合数可能通过某个底数的检验,却无法通过另一个底数的检验。

示例:识别费马伪素数

考虑

341=11⋅31,340=22⋅85.341=11\cdot31,\qquad 340=2^2\cdot85.

以 22 为底时,

285≡32(mod341),2^{85}\equiv32\pmod{341},

下一次平方得到

322≡1(mod341).32^2\equiv1\pmod{341}.

初始值既不是 11,也不是 −1-1,而平方步骤在尚未出现 −1-1 的情况下就得到了 11。因此,米勒–拉宾检验证明了 341341 是合数。

然而,

2340≡1(mod341),2^{340}\equiv1\pmod{341},

所以 341341 能通过较简单的以 22 为底的费马检验。米勒–拉宾检验从中间的幂中提取了更多信息。

11 的这个非平凡平方根还揭示了因数:

gcd⁡(32−1,341)=31,gcd⁡(32+1,341)=11.\gcd(32-1,341)=31, \qquad \gcd(32+1,341)=11.

有时可以这样找出因数,但米勒–拉宾见证底数并不一定能直接给出因数。

示例:通过检验的合数

合数

2047=23⋅892047=23\cdot89

能通过以 22 为底的检验。这里 2046=2⋅10232046=2\cdot1023,并且

21023≡1(mod2047).2^{1023}\equiv1\pmod{2047}.

因此,仅通过一轮检验并不能确定一个数是素数。

错误概率保证及其含义

对于每个奇合数 n>9n>9,在底数 1≤a≤n−11\leq a\leq n-1 中,强说谎底数的数量至多为 (n−1)/4(n-1)/4。更小的奇合数 99 也很容易处理,而采用标准抽样区间 2≤a≤n−22\leq a\leq n-2 时,就能得到通常所说的每轮错误概率至多为 1/41/4 的上界。

对于一个固定的合数输入,以及 kk 个独立、均匀抽样得到的底数,

Pr⁡(all rounds pass∣n is composite)≤4−k.\Pr(\text{all rounds pass}\mid n\text{ is composite}) \leq 4^{-k}.

例如,进行 6464 轮检验时,最坏情况下的上界为

4−64=2−128.4^{-64}=2^{-128}.

这一保证是单侧的:

  • 假设算术运算和实现正确,素数输入总能通过检验。
  • 合数输入可能通过检验,但在上述抽样假设下,通过检验的概率有明确的上界。

用随机算法的术语来说,米勒–拉宾检验是一种具有单侧错误的蒙特卡洛方法。

这一条件概率的条件方向很重要。上述上界并不自动等于被接受的数是合数的概率:

Pr⁡(composite∣passes)\Pr(\text{composite}\mid\text{passes})

还取决于候选数的选取方式,以及其中素数原本所占的比例。它与一个固定合数通过检验的概率是不同的量。

重复检验的概率上界依赖于底数选择的独立性和均匀性。重复使用同一个底数不会提供额外的数学保证;任意选取一些可预测的底数,也不会仅仅因为数量达到 kk 个,就获得 4−k4^{-k} 的保证。

确定性版本

虽然通用的米勒–拉宾检验是随机算法,但在若干情形下,可以将其变为确定性算法。

有界输入范围

对于指定的有限整数范围,有一些经过证明的底数集合,足以区分该范围内的所有素数与合数。例如,检验以下十二个素数底数

2,3,5,7,11,13,17,19,23,29,31,372,3,5,7,11,13,17,19,23,29,31,37

并按通常方式处理较小的输入,就足以检验所有 n<264n<2^{64} 的输入。

使用固定底数列表的实现必须正确处理普通抽样区间之外的底数,例如先将其对 nn 取模,并妥善处理平凡的剩余类。所用的有界范围定理也必须与实际输入范围相符。一个足以处理 64 位整数的底数集合,并不因此就足以处理任意精度整数。

有条件的确定性检验

在某种适当形式的广义黎曼猜想成立的前提下,米勒最初的方法给出了一个确定性多项式时间检验。在这一假设下,每个奇合数都有一个见证底数,其大小不超过 (log⁡n)2(\log n)^2 的某个常数倍,因此只需检查不超过这一上界的所有底数。

如果不采用该假设,目前尚不知道同样的小底数上界是否普遍成立。虽然存在无条件的确定性多项式时间素性检验算法,但它们使用的是不同的方法。

计算成本

设 LL 为 nn 的二进制位数。二进制模幂运算需要 O(L)O(L) 次模乘,随后的平方链也至多需要 O(L)O(L) 次模乘。

因此,采用传统的整数算术算法时,一轮检验需要

O(L3)O(L^3)

次位运算,而 kk 轮检验需要

O(kL3).O(kL^3).

这些表达式使用了大O记号。更快的乘法和模约减方法可以改善位复杂度。更一般地,如果两个 LL 位数的模乘成本为 O(M(L))O(M(L)),则总成本约为 O(kL M(L))O(kL\,M(L))。

许多合数候选值在第一轮就会被排除,因此无需承担全部 kk 轮的计算成本。素数输入会通过每一轮,因此需要完成规定的全部计算。

历史与实际作用

加里·L. 米勒于 1976 年发表了依赖假设的确定性理论基础。迈克尔·O. 拉宾于 1980 年发表了随机化形式,其依据是:对每个奇合数,都有很大一部分底数能够揭示其合数性。

米勒–拉宾检验后来成为生成大型可能素数的标准工具。典型流程是先生成所需位数的候选数,排除能被小素数整除的数,再对剩余候选数进行多轮米勒–拉宾检验。素数定理解释了为什么在大整数中,素数的出现频率仍足以使反复生成候选数的方法切实可行。

该检验有若干重要局限:

  • 可能为素数不等于已经证明是素数。 通过随机轮次的检验只能给出量化的错误概率上界,并不构成一般意义上的素性数学证明。
  • 算术运算必须精确。 即使数学算法本身正确,固定位宽乘法中的溢出也可能导致模运算出错。
  • 底数选择过程是保证的一部分。 对于有偏或相互依赖的选择方式,需要另行分析。
  • 检测见证底数并不等于通用的因数分解。 被拒绝的候选数已知是合数,但其因数可能仍然未知。
  • 固定底数的保证有范围限制。 对经过证明的有限底数集合,不能在没有依据的情况下将其适用范围扩展到已确立的范围之外。

当需要可验证的素性证书时,可以先用米勒–拉宾检验进行初步筛选,再使用独立的素性证明程序。