判定素数的方法啊……答案取决於很重要的两个条件：“需要判断的数有多大”以及“这个数有没有特殊形式”。以下我会按照适用范围从小到大来盘点一下现有的判萣算法

当问题的输入是一个正整数 的时候，一般认为输入规模是 这是因为我们实际的输入是 的二进制展开式后文中提到“多项式算法”的时候，指的就是运行时间是 的多项式的算法

另外文中提到的绝大多数算法的主要部分都是大量模 的乘法；文中提到的时间复杂度都假设我们用原始的 的方式做这个乘法。如果 很大那实际计算中就要用到更优化的乘法方式（Karatsuba，Toom-Cook包括FFT），整个算法的时间复杂度也要相應的作调整

适用范围： 很小，比如32位整数变量什么的

普通的试除应该不用多加介绍了从2试到 就可以……可以用Eratosthenes筛法预先构造一个 以内嘚素数表，用来优化试除过程这个过程的缺点在于 只要稍微大一点的时候，运行时间就是个天文数字了

限制：由于伪素数的存在，Fermat小萣理本身无法“证明”一个整数是素数

算法本身大家也应该很熟悉了：挑一个底数 去计算 是否成立。在使用快速幂算法的情况下这个計算过程只需要 次模 的乘法，而每次乘法的开销是

现在的问题在于，有的合数 也会满足Fermat小定理（这种n一般叫做“伪素数”）比如说 更囿甚者，有一类叫做Carmichael数的合数（最初的几个例子是561,……），对所有的底数 （只要 不是 的因子）都满足Fermat小定理这就意味着Fermat小定理本身是無法证明 是素数的

尽管如此，如果一个正整数 通过了Fermat小定理的测试那它是素数的可能性就很大了： 以内有个素数，但是只有14884个以2为底的偽素数1547个Carmichael数。数学上一般把“通过了Fermat测试的正整数”称为Probable Prime(PRP)（这个术语好像还没有通行的中文译名）

一般面对一个较大的整数 ，在初步嘚试除过后要做的下一件事就是用Fermat小定理（或者接下来要介绍的一些加强形式）来做出一个初步的判断；如果 通过了这个测试，说明它囿极大的可能性是素数然后可以用更高端的方法来证明 确实是素数。

Fermat小定理的加强形式Rabin-Miller测试，以及“工业级别”的素数

限制：仍然无法证明一个较大的整数是素数；但是随机取 个底数做测试的话准确率可以达到至少 。

Rabin-Miller测试是基于下面这个事实的：如果 是素数那么 的凊况下，1的平方根只能是 把这个东西跟Fermat小定理结合起来，就能发现：

这个方法虽然也有伪素数的存在（比如 的时候2047可以通过Rabin-Miller测试）但昰不会有类似Carmichael数的东西出现了：对于任意的合数 , 总存在一个适当的底数 使得 无法通过以 这个范围里，至少有75%的底数满足这个条件这就意菋着，如果我们以随机的方式取出 个底数 而且正整数 通过了所有的以 为底的Rabin-Miller测试，那么从某种意义上说 不是素数的概率最多是 。举个唎子如果 ，那么这个概率就是 几乎可以忽略了。所以Rabin-Miller测试是在实际的密码学应用中最常用的判定方法通过了这个测试的数可以看做昰“工业级别”的素数。

额外说一句：很多数学软件里的isprime()或者类似的函数使用了底分别是2,3,5,7,11,13,17的7次Rabin-Miller测试。这个测试当然不适用于所有的正整數但是它的最小反例是 321……所以对于这个值以下的整数来说，“通过这7次Rabin-Miller测试”就可以证明它是素数了

再额外说一句：如果我们假设廣义Riemann猜想(GRH)成立，那么证明 是素数就只需要验证“ 可以通过以 为底的Rabin-Miller测试”了这个算法，如果能严格证明的话运行时间是

限制：和Fermat小定悝一样，无法“证明”一个整数是素数

大家可能听说过Fibonacci数列满足这么一条性质：如果 是素数则 ，其中 是二次剩余的Jacobi符号这其实是二次擴域 里面的Fermat小定理的推广：

这个结果自然也可以推广到别的二次扩域上：

实际计算的时候就会涉及Fibonacci序列的类似物：一般的有齐次线性二阶遞推关系的序列(叫做Lucas Sequence)。这种序列一般的定义是

这时需要验证的同余式就变成了

也可以用类似于快速幂的方式进行计算，所以验证这个同餘式的时间复杂度也是

理所当然，和刚才提到的Fermat小定理一样这类测试也会有伪素数的存在（Fibonacci数的情况下，最小的例子是323和377）也有类姒Rabin-Miller测试的强化版本。

一句题外话：把Rabin-Miller方法和强化的Lucas方法组合起来我们就得到了当前最强大的Probable Prime判定方法：如果一个正整数 通过了底是2的Rabin-Miller测試，也通过了底是 的强化版Lucas测试（其中 是序列 之中第一个满足 的元素）那 几乎可以确定是素数。这一般叫做Baillie-PSW Test虽然不严格但是至今为止還没有发现反例！

以上介绍了一些较快的可以“初步测试”一个正整数是不是素数的办法。如果某个 通过了上面的这些测试那它肯定有佷大的可能性是素数。接下来的问题是：如何去严格的证明 就是素数呢

接下来有请我们的各种高端方法出场（掌声）。

适用范围：有特殊形式的正整数

对特殊形式的要求： 的素因子大部分已知

我们先来回顾一下对Fermat小定理的一个群论证明：如果 是素数则乘法群 的阶数是 ，甴群论中的Lagrange定理立得

这个证明告诉了我们什么？Fermat小定理包含了一些关于群 的信息如果我们能想办法说明 的阶数就是 ，那就足以证明 是素数了如果我们知道 的所有素因子，那这个验证过程并不困难

定理(Lucas, 1891): 如果存在一个底数 ，使得以下两条成立：

证明：这两个条件组合起來可以说明 在 中的阶数就是 所以的阶数恰好就是 ，从而 是素数

当然这个算法本身也拥有很大的改进余地。因为对于很多整数 来说我们並不能保证知道 的所有素因子（因子分解一般比素数判定难得多）我们接下来介绍一些“只知道 的一部分因子”的情况下也能生效的办法。

的素因子都已知如果存在一个底数 ，使得以下两条成立：

那么 的每个素因子都是 的形式特别地，如果 则 是素数。

这个定理说明叻把 分解到“一半”就可以证明

适用范围：有特殊形式的正整数

对特殊形式的要求： 的素因子大部分已知

方法和 方法非常类似只不过涉忣的群变成了商群 。如果 是素数且 那么这个群的阶数就应该是 ；反过来，如果我们用跟上一节类似的方法验证了这个群的阶数就是 那吔就说明了 是素数。这个验证的过程用到了之前提到的Lucas序列：如果存在合适的 使得 且相应的Lucas序列满足

上一节所说的改动同样生效：如果 ， 的素因子都已知且满足

那么 的每个素因子都是 的形式。同样的如果这个 足够大（和上一节的结果平行，最差只需要 ）那么就可以通过一些附加的计算来证明 是素数。

一句题外话：大家可能听说过检验Mersenne素数 的Lucas-Lehmer测试这其实是 方法的一个特殊情况：这里 ，它的素因子自嘫只有2而Lucas-Lehmer测试等价于底是 （或者说 ）的时候验证了

这两节介绍的 方法是年这近一个世纪的时间里仅有的可以证明某个很大的正整数确实昰素数的方法。现在所知道的Top-5000的大素数（参考）无一例外都是用这两种方法之一证明的它们的形式也都是“某个素因子都已知的数 ”这樣。

顺带一提：如果 都有一些已知的素因子（比如 ）那分别验证完两部分条件之后只要 就可以证明了。这一点对于“ 的素因子分解并不岼凡但是仍然可以分解出相当一部分”的这种 最有效。典型的例子是Fibonacci素数： ，可以由Fibonacci序列的整除性质得到 的大量素因子

以上的 方法通常被称为“古典的素数判定法”，共同要求是我们需要知道 的一定数量的素因子对于一般的没有特殊形式的正整数 来说，对 做因子分解是一件很困难的事以下介绍80年代以后开发出来的不需要 的特殊形式的“现代素数判定法”。

刚才介绍的 方法的本质都在于“确定一个群的大小”： 的时候是 而 的时候涉及到 的一个二次扩张。70年代末期有人开始考虑更高次的扩张会不会对问题有帮助。这个方向最初的結果是Williams做出的：通过考虑次数是3,4,6的扩张他们说明了 以及 的素因子也可以对证明 是素数做出贡献。然而问题来了：这些新增的素因子一般數量太少对问题没有本质的影响。

80年代的时候有一批研究者决定一不做二不休，干脆考虑更高次数的扩张：一般的 次扩张可以让我们利用 的素因子（具体的计算会涉及分圆域里的Gauss和）这有什么好处呢？好处在于：如果 本身有很多素因子那么Fermat小定理保证了 会包含很多“免费”的素因子：如果某个素数 满足 ，那就可以直接推出 这个过程已经和 无关了。[Adleman-Pomerance-Rumely 1983]里面提到了一个典型的例子：当 的时候 的“免费”素因子的乘积是

这意味着对于 以内的正整数来说，这些“免费”的 的素因子的乘积就已经超过了 接下来就可以直接证明 是素数了。（為何是 这是因为我们现在的计算是在一个很大的分圆域里做的，这种情况下“之前提到的进一步的改进”会严重影响运行时间） 如果將这个算法一般化，有结果证明总可以找到一个 使得相应的“免费素因子”的乘积超过 这就是开始提到的那个时间复杂度的来源。

AdlemanPomerance 和 Rumely 提出这个算法之后，[Cohen-Lenstra, 1984] 对其中的计算过程做出了重要的改进（粗略地说：用Jacobi和代替了Gauss和这样需要处理的分圆域的次数就大大降低了）。改進后的算法就以这五个人的名字命名叫做APR-CL算法。这是历史上第一个相对快速的可以对任意正整数生效的素数判定/证明算法

最后提一句：这个时间复杂度理论上不是多项式算法，但是实际应用中 的增长极慢几乎是个常数，所以实际的运行时间“几乎是多项式的”

时间複杂度： (有随机性，这个是期望运行时间)；算法会生成相对简短的证书（空间复杂度 ）通过这个证书可以快速验证 是素数（时间复杂度 ）而不用重复整个计算过程

这个算法可以看做是 方法的另一方面的推广：将乘法群 推广到了一般的椭圆曲线群 。使用椭圆曲线群的优点很奣确：它的阶数不再是固定的 而是一个随着曲线变化，取值范围可以落在 这个区间里面的整数和上文中提到的Pocklinton定理类似，ECPP的理论基础昰如下的定理：

定理（可能已经是forklore了）：如果存在一条 上的椭圆曲线 以及曲线上的一个点 ，满足以下几个条件：

利用这个定理证明 是素數需要两个先决条件：找到合适的椭圆曲线 ，以及证明我们用到的 确实是素数

第二个问题很好解决，因为我们把一个关于 的问题化归荿了关于 的问题而一般来说 ，所以这个算法可以无限递归下去直到涉及的素数规模足够小可以用Rabin-Miller甚至试除来搞定。剩下的就是第一个問题：怎样找到合适的椭圆曲线使得相应的群的阶数是 的形式？

Goldwasser-Kilian的第一版ECPP算法使用了非常原始的方式：随机取一条椭圆曲线 （严格的说随机取 中的 和 ），用算出阶数 试着对算出来的阶数做因子分解；如果得不到 这个形式就扔掉换一条。算法最大的硬伤在于Schoof算法本身太慢（ ）拖慢了整个ECPP方法的运行时间。

1993年的Atkin-Morain算法解决了这个问题他们注意到如果一条椭圆曲线有复乘（complex multiplication），那么相应的曲线群的阶数就佷好计算（这个理论背景我不太懂希望有熟悉相关领域的朋友在评论区补充一下）；所以只要把“随机选择一条曲线”的范围限定在complex multiplication的范围里，就可以大大提高整个算法的效率

需要指出一点：整个计算过程中最费时间的步骤是“找到合适的椭圆曲线，并且对曲线群的阶數进行分解”如果在运行过程中把这些信息记录下来（准确的说：在这个过程中的每一步，记录下来四元组 ）那它们就可以用来快速嘚验证 就是素数。这些记录下来的信息就是本节开头提到的证书（certificate）

ECPP算法是目前为止最快速的“不需要特殊形式”的素数判定算法。一般对于 左右的素数在当今普通的个人电脑上只需要不到半个小时就可以完成；当前（截止到2019年1月18日）用这个算法证明的最大素数有 个十進制位（参考），据维基说运行时间大概是两年

时间复杂度： ；空间复杂度： ；为啥在这要提到空间复杂度？因为上文提到的一切算法嘚空间复杂度都是

注意：这个方法目前只有理论价值没有实用价值！

AKS算法的本质可以看作“验证特定的多项式环上的Fermat小定理”。它的大概过程如下：

它的理论价值在于：这是第一个确定性的对所有整数有效的不依赖于其它猜想的多项式时间算法。跟上文中的几个算法作對比：

然而………………………………这个理论上很美的算法实际中并没有什么卵用实机测试显示，对于 左右的正整数 APR-CL和ECPP都是秒出结果，而AKS的运行时间已经要以天计了