如何编程判断一个数是否是质数？ 第1页

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

注：本文的脉络参考了The Prime Pages上的介绍： https://primes.utm.edu/prove/index.html

写在前面

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

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

naive的试除法

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

对特殊形式的要求：无

时间复杂度：

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

Fermat小定理

适用范围：一切正整数

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

时间复杂度：

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

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

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

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

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

适用范围：一切正整数

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

时间复杂度：

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

• 如果上面一个式子的右端是1，那么就可以继续开平方根得到
• 依次类推，直到左边的指数 是奇数不能再开平方根，或者某一步右边变成了-1为止。
• 如果某一步开平方根的时候右端直接从1变成了“不是 的数”，则 是合数。

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

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

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

Lucas序列

适用范围：一切正整数

限制：和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，虽然不严格但是至今为止还没有发现反例！

-----------------------分割线-------------------

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

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

n-1方法

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

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

时间复杂度：

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

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

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

• 对 的每个素因子 ，都有

那么 是素数。

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

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

定理(Pocklington, 1914): 假设 ，其中 的素因子都已知。如果存在一个底数 ，使得以下两条成立：

• 对 的每个素因子 ，都有

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

这个定理说明了把 分解到“一半”就可以证明 是素数了。后续的一些工作用更加细致的分析把这个“一半”的界限降低到了三分之一 [Brillhart-Lehmer-Selfridge 1975], 30% [Konyagin-Pomerance 1997], 以及 [Coppersmith-Howgrave-Graham, 2008]（后两篇文章的算法需要做一些附加的计算，涉及Lattice Reduce以及LLL算法）。 篇幅所限，此处不做进一步展开，有兴趣的读者可以自行查阅文献。

n+1方法

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

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

时间复杂度：

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

，那么 就是素数。

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

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

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

。

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

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

----------------------70-80年代的分割线------------------------

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

APR-CL算法

适用范围：一切正整数

时间复杂度：

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

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

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

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

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

椭圆曲线算法（Elliptic Curve Primality Proving, ECPP）

适用范围：一切正整数

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

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

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

• ，其中 是素数且 ;
• 在 中，

则 是素数。

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

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

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

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

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

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

AKS算法

适用范围：一切正整数

时间复杂度： ；空间复杂度： ；为啥在这要提到空间复杂度？因为上文提到的一切算法的空间复杂度都是 ，只有AKS不一样

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

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

• 输入一个正整数 。检验 不是其他正整数的幂。
• 找到最小的正整数 使得 在 中的阶数至少是 。
• 一路试除到 。
• 对于所有的 ，验证下面的多项式同余式： 。
• 如果都通过则 是素数。

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

• 方法需要用到 的特殊形式。
• APR-CL算法的时间复杂度不是多项式。
• Rabin-Miller方法依赖于GRH的成立。
• ECPP方法满足上面提到的别的条件，但是涉及到“随机选取椭圆曲线”的过程，所以不是确定性的。

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

最后总结一下

• 如果要判断的正整数 很小（int32），直接试除就好。
• 如果 稍微大一点 ，用7次Rabin-Miller。
• 再大一些的时候，首先用试除和Baillie-PSW做一个初步测试。如果通过了初步测试，再用以下的方法来证明 是素数：
• 如果 很容易做因子分解，用相应的 方法。
• 如果 没有特殊形式，用APRCL或者ECPP。
• 如果只是想满足好奇心，可以试着实现一下AKS……

--------------------------------完结撒花--------------------------