素性检验是一种判定给定整数是否为素数的算法。素数是大于 1 且正因数只有 1 和其本身的整数。素性检验是计算数论的核心问题,也是许多密码系统不可或缺的组成部分。其难度在很大程度上取决于输入的大小和结构,以及所需的结果是判定该数为可能素数,还是给出严格证明。
最简单的检验方法是寻找因数。更先进的方法则检验所有素数都满足的代数恒等式,利用随机选择来检测合数,或构造可供独立核验的证书。这些方法使得检验远超试除法处理能力的大数成为可能。2002 年,曼因德拉·阿格拉瓦尔、尼拉杰·卡亚尔和尼廷·萨克塞纳证明,可以在相对于输入长度的多项式时间内,以确定性算法判定一个数是否为素数,从而解决了一个长期悬而未决的理论问题。
素性检验必须与求一个数的素因数区分开来。素性检验可以证明一个数是合数,却不必找出任何非平凡因数。这一区别解释了为何密码软件能够高效地生成大素数,而对大小相近的素数之积进行因数分解,在计算上仍然十分困难。
判定问题及其计算规模
对于正整数 ,素性判定问题要判断的是:是否有 ,且不存在满足 的整数 能整除 。数字 1 既不是素数,也不是合数;大于 1 而不是素数的整数称为合数。按照初等数学中的标准定义,负整数和零都不是素数。因此,完整的实现应先处理这些基本的边界情况,而不是不加区分地直接使用主要检验方法。
衡量输入规模时,通常采用二进制位数
而不是数值 本身。一个大约需要 次运算的算法,其运算次数随 呈指数增长,因为 近似为 。相比之下,如果一个算法所需的位运算次数为 ,其中 是固定常数,那么它就具有多项式时间复杂度。复杂度的表述使用大O记号等渐近记号,并且必须区分位运算与任意大整数上的运算:两个千位二进制数相乘并不是常数时间操作。
确定性检验不依赖随机选择,对每个允许的输入都能给出正确答案。概率性检验使用随机性,可能以一个有精确上界的概率将合数判为通过。一些重要的检验具有单侧错误:素数总能通过,而合数可能通过某些轮次的检验。通过这类检验的数,相对于所执行的检验而言,称为可能素数。“可能素数”描述的是现有证据,而不是介于素数与合数之间的第三种数学类别。
另一个区别涉及证明证书。素性证书是能够确立某个数为素数的有限数据,可由独立的验证算法进行检查。生成证书可能需要大量搜索或随机选择,而验证过程仍然可以是确定性的。反过来,确定性判定算法未必会生成便于使用、且独立于其执行过程的证书。在对大型计算结果进行独立核查时,这些区别十分重要。
素性判定与整数分解相互关联,但并非同一个问题。分解结果可以立即确定一个数是否为素数,但许多合数见证并不能给出任何因子。在确定性多项式时间判定算法问世之前,人们就已经知道如何构造多项式规模的素性证书:沃恩·普拉特于 1975 年提出的构造利用了 的因子,并递归地为这些因子的素性提供证书。2002 年的 AKS 结果确立了素性判定属于确定性多项式时间复杂度类 P。对于一般的整数分解问题,目前尚无已知的、与之相当的经典多项式时间算法。
试除法、筛法与初等预处理
试除法基于一个基本事实:每个合数 都有一个不大于 的素因子。如果 且 ,则 ,而且必有某个素数整除 。因此,只需检验 能否被不超过 的素数整除。例如,要证明 97 是素数,只需检验 2、3、5 和 7。找到一个因子,既能证明该数为合数,也能提供有用的额外信息。
逐一尝试不超过 的所有整数会浪费计算量。排除偶数候选后,简单的实现只需尝试奇数除数。更精细的轮式分解法会跳过能被若干个小素数整除的剩余类。例如,以 、 和 为基础的轮,在模 30 的 30 个剩余类中只保留 8 个。这能带来常数因子的改进,但试除法的计算量仍随输入的位数呈指数增长。
当需要判断许多小整数是否为素数时,使用埃拉托斯特尼筛法比逐个检验更合适。筛法依次标记各个素数的倍数,最终未被标记的数就是素数。在标准计算模型下,筛出不超过 的所有整数中的素数,需要 次基本标记操作,存储空间与 成正比。分段筛法每次处理较短的区间,在重复使用不超过 的素数的同时,减少工作内存。因此,筛法是一种在给定范围内枚举素数的技术,不过它也能为单个整数的检验提供试除所需的除数。
对于较大的输入,试除法通常用作预处理,而非完整的检验方法。若某个候选数能被 3 或 5 整除,就应在执行数百次大整数模乘之前将其排除。如果要检验许多彼此相近的候选数,可以通过增量方式更新它们模各个小素数的余数。有些实现会将若干小素数相乘,合并成可容纳于一个机器字中的乘积,使多次整除检验能够共用算术运算。试除到何处最为合适,取决于整数大小、硬件以及后续检验的开销。
完全幂是另一类值得在预处理中检测的数。如果对整数 和 ,有 ,那么即使不知道 是否为素数,也能断定 为合数。精确的整数开根算法可以检测这类情况,避免浮点运算中舍入所造成的不确定性。只需检查不超过 的素数指数,因为合数指数必有素因子。对于后续论证假定输入不是非平凡整数幂的理论算法,完全幂检测尤为重要。
费马检验与同余证据的局限
费马小定理指出,若 是素数,且 不能被 整除,则
这一恒等式将素性检验转化为模算术中的问题。给定一个待检验的奇数 ,选取满足 的 ,计算它与 的最大公约数,再求出 。非平凡的最大公约数会直接给出一个因子。若最大公约数为 1,但同余式不成立,则 一定是合数。
计算大整数幂时,使用的是模幂运算,而不是先算出完整的整数 。反复平方法逐位处理指数的二进制表示,只需进行 次模乘运算。每次乘法之后,都可以将中间结果对 取模。这是许多实用素性检验背后的基本计算机制:由于余数始终有界,即使指数极大,计算也能变得切实可行。
通过费马检验并不能证明一个数是素数。合数
满足 ,因此它是以 2 为底的费马伪素数。使用“伪素数”一词时,必须说明所依据的检验,通常还要指明所用的底数:一个合数可能在某个同余关系下表现得像素数,却无法通过另一个同余关系的检验。对于任意固定的底数,都有无穷多个合数能通过相应的费马检验,因此,即使输入的数越来越大,单次固定底数检验也无法给出确定结论。
更根本的障碍是卡迈克尔数,即对每个与 互素的 都满足费马同余式的合数 。最小的卡迈克尔数是
1899 年提出的科塞尔特判据刻画了这类数:合数 是卡迈克尔数,当且仅当它不含平方因子,且对于 的每个素因子 ,都有 整除 。1994 年,W. R. 奥尔福德、安德鲁·格兰维尔和卡尔·波默兰斯证明了卡迈克尔数有无穷多个。
因此,反复使用与待检验数互素的底数进行普通费马检验,并不能得到一个随检验轮数按几何级数递减的通用错误概率上界。卡迈克尔数能通过每一轮这样的检验。费马检验仍可用作快速排除合数的筛选手段,也具有概念上的基础意义;但更强的检验会考察模素数乘法运算中的其他结构。具体而言,它们会检查计算过程中出现的 1 的平方根,而不只是最终的幂运算结果。
米勒—拉宾强伪素数检验
米勒—拉宾素性检验利用域中方程 的解只有 和 这一事实,强化了费马检验。对于奇数候选数 ,将其写成
对于满足 的底数 ,计算 。如果 或 ,则通过本轮检验。否则,对 反复平方,最多进行 次;若出现 ,则通过本轮检验。
素数总能通过检验。根据费马定理,反复平方最终会得到 1;如果初始值不是 1,那么在首次出现 1 之前的那个值必定是 。当模数为合数时,1 可能存在非平凡平方根。一旦遇到这样的平方根,就证明了该数是合数,而且还可能通过 找到一个因数。另一种情况是,序列始终未达到所要求的值,因而未能通过本轮检验,但并不直接给出因数。
对于任意奇合数 ,在 中,至多四分之一的底数是强伪证底数,即会使该数通过检验的底数。因此,独立、均匀地选取底数进行 轮检验,误判为素数的概率至多为
这一上界对每一个固定的合数输入都成立,并不假设输入服从某种随机分布。进行四十轮独立检验,便可得到 的误判概率上界。该上界依赖于正确的底数选取方式以及各轮之间的独立性,而不是简单地将同一轮检验重复多次。
从历史上看,需要区分两个相关结果。加里·米勒在 1976 年的工作中,以适当形式的广义黎曼猜想成立为前提,给出了一种确定性多项式时间检验。迈克尔·拉宾在 1980 年的工作则确立了随机化版本及其无条件的误差保证。在相关猜想成立的条件下,对于每一个合数输入,足够小的底数中必定包含一个能揭示其合数性的见证底数,从而使确定性搜索的上界达到 量级。如果不以该猜想为前提,仅检验一组便于使用的少量底数,并不能为任意大的整数提供普遍有效的素性证明。
不过,对于有界的机器整数,可以借助数论界限和穷举计算,证明某些有限底数集合足以完成判定。这类保证取决于 的确切上限,不能将已证实适用于某个有限范围的底数列表用于不受范围限制的整数。在多精度运算库中,米勒—拉宾检验因其简单、快速、易于重复,且在筛除小因数后效果良好而得到广泛应用。不过,其输出仍应区分“已证明为素数”和“已通过指定轮次的可能素数检验”。
欧拉–雅可比测试与卢卡斯序列测试
1977 年提出的 Solovay–Strassen 测试使用欧拉判别法,而非 Miller–Rabin 测试中的平方根链。对于奇素数 和不能被 整除的整数 ,有
其中右侧为勒让德符号。对于奇合数候选数 ,则用能够高效计算的雅可比符号 替代勒让德符号。两侧不相等即可证明该数为合数。
对于每个奇合数输入,符合条件的底数中至多有一半能通过欧拉–雅可比检验。因此,独立重复 轮后,错误概率的上界为 。该算法有助于确立随机化计算的实际意义,但通常更倾向于采用 Miller–Rabin 测试,因为后者每轮的最坏情况错误概率上界更低,实现开销也较小。雅可比符号本身可用类似欧几里得算法的算法计算,无须对 进行因数分解。
另一类测试使用卢卡斯序列。给定整数 ,定义
并令 。对于不整除 的奇素数 ,有
这一恒等式取决于判别式为 的二次多项式是在含 个元素的域上分裂,还是仅在其二次扩域上分裂。利用高效的倍增公式,只需对数数量级的模运算,就能求出序列中下标很大的项。
卢卡斯可能素数测试用雅可比符号替代勒让德符号,并检验相应的恒等式在模候选数 的意义下是否成立。强卢卡斯测试将相关下标分解为一个奇数与 2 的幂的乘积,这与 Miller–Rabin 测试有些类似。参数选择是测试定义中不可或缺的一部分: 的不同取值、不同的判别式搜索规则和接受条件,会产生不同的测试及不同的伪素数集合。
Baillie–PSW 测试将以 2 为底的强可能素数测试与卢卡斯可能素数测试相结合,并辅以完全平方数检测等预备检查;其中的卢卡斯测试通常采用按 Selfridge 方法选取参数的强卢卡斯测试。目前尚未发现能通过这一标准组合测试的合数反例。然而,没有已知反例并不等于证明了反例不存在,也不能将假定相互独立的失败概率相乘,就自动得到这一组合测试的数值误差估计。它的各个组成部分都是输入的确定性函数,并没有一般性的独立性定理作为保证。
利用相邻整数的因子证明素性
要证明 是素数,一种强有力的方法是掌握 的足够多的因子分解信息。其背后的原理是群论中的乘法阶。设 是 的一个素因子,如果模 的剩余类 的阶能被一个较大的整数 整除,那么 ,因此 。如果每个素因子都必须大于 ,那么候选数就不可能是合数。与试除法不同,这种证明无需逐一枚举所有可能的因子,就能对它们施加约束。
波克林顿判据的一种标准形式将 写成
其中, 的完整素因子分解已知,且 。对于每个不同的素数 ,假设都存在一个整数 ,使得
且
那么 就是素数。不同的素因子 可以使用不同的见证数 。
下面说明其原理。设 是 的任意一个素因子。第一个同余式保证 的阶整除 ;最大公因数条件则保证这个阶不整除 。因此,这个阶必须包含 的素因子分解中 的完整幂次。综合所有 对应的约束,就可推出 。于是,每个素因子 都大于 ,而合数不可能满足这一条件。
例如,要证明 101 是素数,可以利用 ,并取 。 只有一个不同的素因子,即 5。见证数 满足
且 。在已知 5 是素数的前提下,这些计算便足以证明 101 是素数,无需对每一个可能的因子进行试除。
普拉特证书递归地运用了类似的思路,提供 的素因子分解、合适的阶见证数,以及其中涉及的较小素数的证书。递归在 2 处终止。这类证书既有计算意义,也有逻辑意义:素性具有简短且可独立核验的证明。困难在于获得所需的因子分解;通用的素性检验不能假定 很容易分解。
与之相应的另一类判据利用 的因子,通常借助卢卡斯数列以及阶与 相关的代数群。更复杂的方法则综合利用相邻整数的部分信息。当候选数经过特意构造,使 或 的很大一部分已有已知的因子分解时,这些检验尤其有效。它们也是递归生成已证素数的基础:构造过程本身提供了素性证明所需的依据,而任意给定的输入未必具备这些依据。
椭圆曲线与分圆素性证明
椭圆曲线素性证明通常缩写为 ECPP,它用有限域上椭圆曲线的点群,替代结构相对受限、阶为 的乘法群。同一有限域上的不同曲线具有不同的群阶。这种灵活性使证明算法能够寻找具有足够大素因子的群阶,而不必局限于某个固定相邻整数的因数分解。
对于定义在含 个元素的域上的椭圆曲线 ,哈塞界给出
假设在满足必要的非退化条件下,模候选数 的计算确定了某个点的阶可被一个已获素性证明的素数 整除。那么,对 的每个素因子 取模约化后,都可推出 整除相应的曲线群阶。如果
那么哈塞界就排除了所有 的可能性,从而证明 为素数。
典型的证书步骤会提供一条曲线、一个点 、一个整数 ,以及一个大素因子 。它验证 是单位元,并且 在模 的每个素因子约化后仍不为单位元。在射影坐标下,后一个要求须通过适当的互素性检验来保证,而不能仅凭观察到某个坐标模 非零。同样,也必须保证曲线在模每个素因子约化后均非奇异,通常通过检验判别式与 互素来实现。
该方法递归地证明 的素性,从而生成一条逐级递减的证书链。莎菲·戈德瓦瑟与乔·基利安于 1986 年提出了一种基于椭圆曲线的素性证明方法;A. O. L. 阿特金则发展了复乘策略,成为广泛使用的实用 ECPP 实现的基础;弗朗索瓦·莫兰在实现和算法方面作出了重要贡献。复乘法有助于构造具有预定候选群阶的曲线,从而避免在每一步都对任意曲线计算点数。验证证书远比寻找证书简单。
另一大类方法是分圆素性证明,与伦纳德·阿德尔曼、卡尔·波默伦斯、罗伯特·鲁梅利、亨利·科恩和亨德里克·伦斯特拉等人的工作有关。APR 和 APR-CL 方法利用涉及单位根和雅可比和的算术运算,对可能存在的素因子施加强有力的限制。在 AKS 算法出现之前,它们提供了重要的通用确定性检验方法,其中某些适当版本具有接近多项式的理论复杂度界。
ECPP 和分圆方法体现了数学复杂度与实际生成证明之间的区别。一个方法即使具有出色的渐近理论结果,在现实规模下也未必最快;而基于搜索的证明算法,即便没有同样简明的无条件最坏情况复杂度界,也可能表现极佳。无论寻找证书时采用了怎样的启发式选择,经过严格核验的 ECPP 证书始终是一份证明。
AKS确定性多项式时间算法
AKS素性检验的基础是用多项式刻画素数。若 是素数,则由二项式定理可得
所有中间项的二项式系数都能被 整除,且 。反过来,对于 且 的情形,不对多项式次数作约简时,上述恒等式成立当且仅当 为素数。直接检查所有系数需要处理一个次数为 的多项式,因此,这种直观方法所需的时间相对于输入长度呈指数增长。
AKS同时对 和 取模,在商环
中进行运算。这样,多项式的次数便被约简到 以下。其关键成果在于证明:排除某些特殊情形后,只需选取一个适当的小整数 ,并验证数量有界的一组同余式
就足以确定 的素性。
算法的一种标准表述首先排除完全幂。然后,寻找一个与 互素的整数 ,使 模 的乘法阶大于 。计算 与一些小整数的最大公约数,可能立即判定它是合数;经过相应检查后,若 ,便可确定它是素数。否则,算法会对从 1 到某个上界的所有正整数 验证上述多项式同余式,该上界涉及 ,其中 为欧拉函数。
证明将乘法阶条件与计数论证结合起来。如果一个不是完全幂的合数 通过了所有同余检验,那么这些同余关系就会在适当的代数结构中生成过多互异的元素。乘法阶条件提供了足够的独立性,从而导出矛盾。这也解释了为什么少数几个类似费马定理的数值同余式不足以判定素性,而一组结构经过精心设计的多项式同余式却能给出确定结论。
阿格拉瓦尔、卡亚尔和萨克塞纳于2002年8月公布了这一结果;论文《PRIMES is in P》于2004年发表于《数学年刊》。该算法无须依赖任何未经证明的假设,具有确定性,运行时间为 的多项式。后续分析和变体进一步改进了其运行时间界。这些进展解决了一个基础性问题,但并未使AKS成为生成素数的常用选择。
它在实际应用中的劣势,在于需要反复进行模 的多项式运算,涉及大量大整数运算,而不是少量普通的模幂运算。对于常见的数值规模,可能素数检验和能生成证书的方法通常表现更好。因此,AKS的重要性主要在于它确立了素性可以高效判定这一理论结果,而非充当多精度算术库的默认算法。
具有特殊结构的数的测试
对于某些特殊形式的数,可以采用远快于通用方法的测试。梅森素数的形式为 。指数 本身必须是素数,因为当指数为合数时,该式可以进行代数因式分解。但指数为素数并非充分条件:。尽管如此,这种形式仍允许使用一种极其简单的确定性测试。
对于奇素数指数 ,卢卡斯–莱默测试从以下递推式开始:
则有
当 时,模 31 的余数依次为 ,由此证明 31 是素数。 时得到的数是 3,这一情形需单独处理。爱德华·卢卡斯于十九世纪提出了其基本思想,德里克·亨利·莱默则在二十世纪完善了这一测试。
梅森数的运算还具有计算上的优势:由于 ,在模约减过程中,可以将二进制高位部分折回并加到低位。面向大数的实现将这一结构与快速乘法相结合,包括与快速傅里叶变换相关的变换方法。这些效率优势解释了梅森数为何在超大素数的搜索中占据突出地位。在这样的计算规模下,需要通过独立运行和错误检测机制来应对硬件故障或运算错误的可能性。
对于形如
的数,普罗斯定理给出了另一种简洁的判定准则。如果存在整数 满足
那么 是素数。反过来,这种形式的素数也必然存在满足条件的见证。 中已知的较大 2 的幂因子,会迫使任何素因子都大到足以排除 为合数的可能。例如,,且 ,因此该准则证明了 13 是素数。
费马数的形式为 。佩潘测试指出,当 时,
表达式简单并不意味着这些数都是素数:欧拉证明了 能被 641 整除。佩潘测试可以在不给出因子的情况下判定一个数为合数。
这些判定准则都离不开各自的前提条件。将卢卡斯–莱默递推式用于任意奇数,或者在不满足 的大小条件时使用普罗斯同余式,都不能保证上述定理仍然成立。它们的速度优势来自对特定代数结构的利用,而非某种普遍适用的捷径。
素数生成、密码学与计算可靠性
素性检验是公钥密码学中的关键步骤。RSA密码系统的密钥生成使用大素数,并以它们的乘积作为公开模数。其他系统则利用素数来定义有限域,或构造具有指定子群阶的群。不同系统的计算要求各不相同:RSA所用的素数不必具备有限域离散对数系统所用模数的那些结构性质。素性检验只能确认所需性质中的一项。
素数定理解释了随机生成候选数为何可行。在大数 附近,素数的密度约为 ;在奇数候选数中,这一密度约为 。对于均匀抽取的 位奇整数,忽略低阶影响后,这意味着平均每找到一个素数,需要考察约
个候选数。当 时,估计需要约355个奇数候选数。小素数筛法会在执行开销较大的可能素数检验轮次之前排除大多数合数,因此,这并不是通常需要执行的完整检验次数。
素数生成流程通常先选择一个具有所需位数的奇数候选数,排除含有小素因子的数,再运行一种或多种可能素数检验,并进行其他必要的结构检查。如果要求得到经过证明的素数,流程随后可以调用ECPP,或利用 的已知因子进行递归构造。生成指定形式的候选数会改变其分布,因此,上述初等密度估计并不能不加调整地适用于所有构造方法。
错误概率需要谨慎解读。米勒–拉宾检验的 界限描述的是某个固定合数通过随机检验轮次的概率。它并不自动等于通过检验的候选数为合数的后验概率;后者取决于候选数的分布以及素数所占的比例。对于多个合数候选数,若进行 次各含 轮、随机选择彼此独立的检验,则由并集界可知,至少出现一次误接受的概率至多为 。对于特定的生成模型,还存在更强的平均情形界限,但它们不同于适用于所有输入的最坏情形保证。
实现的正确性与定理本身同样重要。模乘运算必须妥善处理溢出;底数抽样必须覆盖预定范围,且不能引入非预期的偏差;精确比较必须正确处理较小的输入和2的幂。在对抗性环境中,恶意选择的候选数可能利用规范不够严密的固定底数流程中的弱点。因此,检验说明必须明确所用的变体、底数或抽样规则、预处理步骤,以及适用的输入范围。
若要使结果能够得到独立验证,证明证书可以将对大型搜索程序的信任与对较小验证器的信任分离开来。验证器检查的是精确的算术恒等式和递归的素性断言,而不是直接接受程序给出的最终判定。形式验证还能进一步将这些检查与经过机器核验的定理联系起来。在大规模计算中,可复现性还取决于是否保存了确切的候选数、证书数据和验证条件;如果日志仅记载某个数“通过了素性检验”,就无法明确究竟确立了什么数学结论。