AKS质数测试

AKS质数测试（又称Agrawal–Kayal–Saxena质数测试和Cyclotomic AKS test）是一个决定型质数测试演算法，由三个来自印度坎普尔理工学院（英语：Indian Institute of Technology Kanpur）的计算机科学家，曼宁德拉·阿格拉瓦尔（英语：Manindra Agrawal）、尼拉吉·卡亚尔（英语：Neeraj Kayal）和尼汀·沙克谢纳（英语：Nitin Saxena），在2002年8月6日发表于一篇题为质数属于P的论文。^[1]作者们因此获得了许多奖项，包含了2006年的哥德尔奖和2006年的富尔克森奖。这个演算法可以在多项式时间之内，决定一个给定整数是质数或者合数。

重要性

AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的质数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。

AKS算法可以被用于检测任何一般的给定数字是否为质数。很多已知的高速判定算法只适用于满足特定条件的质数。例如，卢卡斯-莱默检验法仅对梅森质数适用，而Pépin测试（英语：Pépin's test）仅对费马数适用。
算法的最长运行时间可以被表为一个目标数字长度的多项式。ECPP和APR能够判断一个给定数字是否为质数，但无法对所有输入给出多项式时间范围。
算法可以确定性地判断一个给定数字是否为质数。随机测试演算法，例如米勒-拉宾检验和Baillie–PSW，可以在多项式时间内对给定数字进行校验，但只能给出概率性的结果。
AKS算法并未“仰赖”任何未证明猜想。一个反例是确定性米勒检验：该算法可以在多项式时间内对所有输入给出确定性结果，但其正确性却基于尚未被证明的广义黎曼猜想。

概念

AKS质数测试主要是基于以下定理：整数n (≥ 2)是质数，若且唯若

(x+a)^{n}\equiv (x^{n}+a){\pmod {n}}

1

这个同馀多项式对所有与n互质的整数a均成立。这个定理是费马小定理的一般化，并且可以简单的使用二项式定理跟二项式系数的这个特征:

{n \choose k}\equiv 0{\pmod {n}}

，对任何

0<k<n

，若且唯若 n 是质数

来证明出此定理。

虽然说关系式 (1) 基本上构成了整个质数测试，但是验证花费的时间却是指数时间。因此，为了减少计算复杂度，AKS改为使用以下的同馀多项式：

(x+a)^{n}\equiv (x^{n}+a){\pmod {x^{r}-1,n}}

2

这个多项式与存在多项式f与g，令:

(x+a)^{n}-(x^{n}+a)=(x^{r}-1)g+nf

3

意义是等同的。

这个同馀式可以在多项式时间之内检查完毕。这里我们要注意所有的质数必定满足此条件式（令g = 0则 (3) 等于 (1)，因此符合n必定是质数）。然而，有一些合数也会满足这个条件式。有关AKS正确性的证明包含了推导出存在一个够小的r以及一个够小的整数集合A，令如果此同馀式对所有A里面的整数都满足，则n必定为质数。

历史以及运算时间

在上文引用的论文的第一版本中，作者们证明了算法的渐近时间为O $(\log ^{12}(n))$ 。换言之，算法使用少于n的二进制数字长度的十二次方。但是，论文证明的时间上界却过于宽松；事实上，一个被普遍相信的关于索菲热尔曼质数分布的假设如果为真，则会立即将最坏情况减至O $(\log ^{6}(n))$ 。

在这一发现后的几个月中，新的变体陆续出现（Lenstra 2002, Pomerance 2002, Berrizbeitia 2003, Cheng 2003, Bernstein 2003a/b, Lenstra和Pomerance 2003）并依次提高了算法的速度（以改进幅度为序）。由于这些变体的出现，Crandall和Papadopoulos在其科学论文“AKS-类质数测试的实现”（2003年三月发表）中将其称为算法的“AKS-类”。

出于对这些变体和其他回复的回应，论文“质数属于P”稍后被进行了更新，新版本包括了一个AKS算法的正规公式化表述和其正确性证明。（这一版本在数学年刊上发表。）虽然基本思想没有变化， $r$ 却被采用了新方法进行选择，而正确性证明也变得更加紧致有序。与旧证明依赖于许多不同的方法不同，新版本几乎只依赖于有限域上的分圆多项式的特征。新版本同时也优化了时间复杂度的边界到O $(\log ^{10.5}(n))$ 。通过筛法获得的其他结果可以将其进一步简化到O $(\log ^{7.5}(n))$ 。

在2005年，Carl Pomerance和H. W. Lenstra, Jr.展示了一个AKS的变体，可以在 $O(\log ^{6}(n))$ 次操作内完成测试（ $n$ 是被测试数）。对于原算法的 $O(\log ^{12}(n))$ 边界而言，这是一个显著的改进。^[2]

演算法

整个演算法的操作如下：^[1]

输入：整数 n > 1

若存在整数a > 0 且b > 1 ，令 n = a^b ；则输出合数
找出最小的 r 令 ord_r(n) > log²(n).
若对某些a ≤ r，1 < gcd(a,n) < n，输出合数。(gcd是指最大公因数)。
若 n ≤ r, 输出质数。
对 a = 1 到 $\scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor$ 的所有数，
如果 (X+a)ⁿ≠ Xⁿ+a (mod X^r − 1,n), 输出合数。
输出质数。

这里的 ord_r(n)是n mod r的阶。另外，这里的log 代表以二为底的对数， $\scriptstyle \varphi (r)$ 则是r的欧拉函数。

下面说明若n是个质数，那么算法总是会返回质数：由于n是质数，步骤1和3永远不会返回合数。步骤5也不会返回合数，因为(2)对所有质数n为真。因此，算法一定会在步骤4或6返回质数。

对应地，如果n是合数，那么算法一定返回合数：如果算法返回质数，那么则一定是从步骤4或6返回。对于前者，因为n ≤ r， n必然有因子a ≤ r符合1 < gcd(a,n) < n，因此会返回合数。剩馀的可能性就是步骤6，在文章^[1]中，这种情况被证明不会发生，因为在步骤5中检验的多个等式可以确保输出一定是合数。

例子：n = 31为质数

输入：整数n = 31 > 1。

  若存在整數a > 0 且b > 1 ，令 n  =  a^b ；則輸出「合數」。
    for ( b = 2; b < =  log₂(n); b +  +  ){
      a = n^1/b;
      If ( a是整數 ) 輸出「合數」;
    }
    // a = n^1/2...n^1/4 = {5.568, 3.141, 2.360}，計算結果不是整數

  找出最小的 r 令 ord_r(n) > log²(n)。
    nextR = True;
    r = 1;
    while ( nextR =  = True ) {
      r +  + ;
      nextR = False
      for ( k = 1;(!nextR) &&k ≤ log²(n); k +  +  ){
        nextR = (n^k % r =  = 1 || n^k % r =  = 0);
      }
    }
    // 計算結果為：r  =  29

  若 對某些a ≤ r，1 < gcd(a,n) < n，輸出「合數」。
    for ( a = r; a > 1; a-- ){
      If ( 1 < gcd(a,n) < n ) 輸出「合數」;
    }
     
    // gcd(29,31) = 1, gcd(28,31) = 1, ..., gcd(2,31) = 1，計算結果為找不到符合的a使得1 < gcd(a,n) < n為真

  若 n ≤ r, 輸出「質數」。
    If ( n ≤ r ) 輸出「質數」;
     
    // 31 > 29，計算結果n比r大

  對 a  =  1 到  $\scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor$ 的所有數，
     如果 (X + a)ⁿ≠ Xⁿ + a (mod X^r − 1,n), 輸出「合數」。
     
    for ( a = 1; a ≤  $\scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor$ , a +  +  )
      if ( ((X + a)ⁿ-(Xⁿ + a)) % (X^r−1,n) ≠ 0 ) 輸出「合數」。
    }
     
    / *  *  * 
    (x + a)³¹ % (x²⁹-1,31)
      = (((x + a)²⁹ % (x²⁹-1,31)) * (x + a)² % 31) % (x²⁹-1,31)
      = ((1 + a²⁹ + 29a²⁸x + (406 % 31)a²⁷x² + (3654 % 31)a²⁶x³ + (23751 % 31)a²⁵x⁴ + (118755 % 31)a²⁴x⁵ + (475020 % 31)a²³x⁶ + (1560780 % 31)a²²x⁷ + (4292145 % 31)a²¹x⁸ + (10015005 % 31)a²⁰x⁹ + (20030010 % 31)a¹⁹x¹⁰ + (34597290 % 31)a¹⁸x¹¹ + (51895935 % 31)a¹⁷x¹² + (67863915 % 31)a¹⁶x¹³ + (77558760 % 31)a¹⁵x¹⁴ + (77558760 % 31)a¹⁴x¹⁵ + (67863915 % 31)a¹³x¹⁶ + (51895935 % 31)a¹²x¹⁷ + (34597290 % 31)a¹¹x¹⁸ + (20030010 % 31)a¹⁰x¹⁹ + (10015005 % 31)a⁹x²⁰ + (4292145 % 31)a⁸x²¹ + (1560780 % 31)a⁷x²² + (475020 % 31)a⁶x²³ + (118755 % 31)a⁵x²⁴ + (23751 % 31)a⁴x²⁵ + (3654 % 31)a³x²⁶ + (406 % 31)a²x²⁷ + 29ax²⁸) * (a² + 2ax + x²)) % (x²⁹-1,31)
      = ((1 + a²⁹ + 29a²⁸x + 3a²⁷x² + 27a²⁶x³ + 5a²⁵x⁴ + 25a²⁴x⁵ + 7a²³x⁶ + 23a²²x⁷ + 9a²¹x⁸ + 21a²⁰x⁹ + 11a¹⁹x¹⁰ + 19a¹⁸x¹¹ + 13a¹⁷x¹² + 17a¹⁶x¹³ + 15a¹⁵x¹⁴ + 15a¹⁴x¹⁵ + 17a¹³x¹⁶ + 13a¹²x¹⁷ + 19a¹¹x¹⁸ + 11a¹⁰x¹⁹ + 21a⁹x²⁰ + 9a⁸x²¹ + 23a⁷x²² + 7a⁶x²³ +  25a⁵x²⁴ + 5a⁴x²⁵ + 27a³x²⁶ + 3a²x²⁷ + 29ax²⁸) * (a² + 2ax + x²)) % (x²⁹-1,31)
      = ((1 + 2 * 29 + 3) % 31)a² + a³¹ + ((2 + 29) % 31)ax + ((29 + 2 * 1) % 31)a³⁰x + x² + ((3 + 2 * 29 + 1) % 31)a²⁹x² + ((27 + 2 * 3 + 29) % 31)a²⁸x³ + ((5 + 2 * 27 + 3) % 31)a²⁷x⁴ + ((25 + 2 * 5 + 27) % 31)a²⁶x⁵ + ((7 + 2 * 25 + 5) % 31)a²⁵x⁶ + ((23 + 2 * 7 + 25) % 31)a²⁴x⁷ + ((9 + 2 * 23 + 7) % 31)a²³x⁸ + ((21 + 2 * 9 + 23) % 31)a²²x⁹ + ((11 + 2 * 21 + 9) % 31)a²¹x¹⁰ + ((19 + 2 * 11 + 21) % 31)a²⁰x¹¹ + ((13 + 2 * 19 + 11) % 31)a¹⁹x¹² + ((17 + 2 * 13 + 19) % 31)a¹⁸x¹³ + ((15 + 2 * 17 + 13) % 31)a¹⁷x¹⁴ + ((15 + 2 * 15 + 17) % 31)a¹⁶x¹⁵ + ((17 + 2 * 15 + 15) % 31)a¹⁵x¹⁶ + ((13 + 2 * 17 + 15) % 31)a¹⁴x¹⁷ + ((19 + 2 * 13 + 17) % 31)a¹³x¹⁸ + ((11 + 2 * 19 + 13) % 31)a¹²x¹⁹ + ((21 + 2 * 11 + 19) % 31)a¹¹x²⁰ + ((9 + 2 * 21 + 11) % 31)a¹⁰x²¹ + ((23 + 2 * 9 + 21) % 31)a⁹x²² + ((7 + 2 * 23 + 9) % 31)a⁸x²³ + ((25 + 2 * 7 + 23) % 31)a⁷x²⁴ + ((5 + 2 * 25 + 7) % 31)a⁶x²⁵ + ((27 + 2 * 5 + 25) % 31)a⁵x²⁶ + ((3 + 2 * 27 + 5) % 31)a⁴x²⁷ + ((29 + 2 * 3 + 27) % 31)a³x²⁸
      = a³¹ + x²
     
    (x³¹ + a) % (x²⁹-1,31) = a + x²
     
    (a³¹ + x²)-(a + x²) = a³¹-a
     
     ${\sqrt {\varphi (r)}}\log _{2}(n)={\sqrt {28}}*\log _{2}(31)=26.215$ 
     
    (1³¹-1) % 31 = 0, (2³¹-2) % 31 = 0, (3³¹-3) % 31 = 0, ..., (26³¹-26) % 31 = 0，計算結果為找不到符合的a使得(X + a)ⁿ≠ Xⁿ + a (mod X^r − 1,n)為真
     *  *  * /

  輸出「質數」。
    31必為質數。

注释

^ ^1.0 ^1.1 ^1.2 Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P （页面存档备份，存于互联网档案馆）", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
^ 亨德里克·伦斯特拉 and Carl Pomerance, "Primality Testing with Gaussian Periods （页面存档备份，存于互联网档案馆）", preliminary version July 20, 2005.

延伸阅读

Dietzfelbinger, Martin. Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P. Lecture Notes in Computer Science 3000. Berlin: 施普林格科学+商业媒体. 2004. ISBN 3-540-40344-2. Zbl 1058.11070.

外部链接

埃里克·韦斯坦因. AKS Primality Test. MathWorld.
R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
Article by Borneman, containing photos and information about the three Indian scientists（页面存档备份，存于互联网档案馆） (PDF)
Andrew Granville: It is easy to determine whether a given integer is prime（页面存档备份，存于互联网档案馆）
The Prime Facts: From Euclid to AKS（页面存档备份，存于互联网档案馆）, by Scott Aaronson (PDF)
The PRIMES is in P little FAQ（页面存档备份，存于互联网档案馆） by Anton Stiglic
2006 Gödel Prize Citation
2006 Fulkerson Prize Citation（页面存档备份，存于互联网档案馆）
The AKS "PRIMES in P" Algorithm Resource（页面存档备份，存于互联网档案馆）
Grime, Dr. James. Fool-Proof Test for Primes - Numberphile (video). 布雷迪·哈兰. [2018-05-10]. （原始内容存档于2018-03-23）. [the video describes the exponential time relation (1), which it calls AKS]

[AKS-1] 1.0 ^1.1 ^1.2 Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P （页面存档备份，存于互联网档案馆）", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.

[lenstra_pomerance_2005-2] 亨德里克·伦斯特拉 and Carl Pomerance, "Primality Testing with Gaussian Periods （页面存档备份，存于互联网档案馆）", preliminary version July 20, 2005.

[1]

[2]

查论编数论算法
素数测试	AKS APR（英语：Adleman–Pomerance–Rumely primality test） Baillie–PSW（英语：Baillie–PSW primality test）椭圆曲线（英语：Elliptic curve primality） Pocklington（英语：Pocklington primality test）费马卢卡斯（英语：Lucas primality test）卢卡斯-莱默 Lucas–Lehmer–Riesel（英语：Lucas–Lehmer–Riesel test）普罗斯 Pépin（英语：Pépin's test）二次Frobenius（英语：Quadratic Frobenius test） Solovay–Strassen（英语：Solovay–Strassen primality test）米勒-拉宾
质数生成（英语：Generating primes）	阿特金筛法（英语：Sieve of Atkin）埃拉托斯特尼筛法 Pritchard筛法（英语：Sieve of Pritchard） Sundaram筛法（英语：Sieve of Sundaram）轮式因数分解法（英语：Wheel factorization）
整数分解	连分数分解 (CFRAC)（英语：Continued fraction factorization） Dixon's（英语：Dixon's factorization method） Lenstra椭圆曲线 (ECM)（英语：Lenstra elliptic-curve factorization）欧拉因式分解法波拉德ρ算法（英语：Pollard's rho algorithm） p − 1（英语：Pollard's p − 1 algorithm） p + 1（英语：Williams's p + 1 algorithm）二次筛选法普通数域筛选法特殊数域筛选法 (SNFS)（英语：Special number field sieve）有理筛选法费马因式分解法（英语：Fermat's factorization method） Shanks二次形式（英语：Shanks's square forms factorization）试除法秀尔演算法
乘法算法	古埃及乘算（英语：Ancient Egyptian multiplication）长乘法卡拉楚巴算法图姆-库克算法颂哈吉-施特拉森演算法富尔算法（英语：Fürer's algorithm）
欧几里德除法除法算法	二进制（英语：Binary division）倍块法（英语：Chunking (division)） Fourier（英语：Fourier division） Goldschmidt（英语：Goldschmidt division） Newton-Raphson（英语：Newton–Raphson division）长除法短除法 SRT
离散对数	大步小步算法波拉德ρ算法 Pollard kangaroo（英语：Pollard's kangaroo algorithm） Pohlig–Hellman（英语：Pohlig–Hellman algorithm） Index calculus（英语：Index calculus algorithm） Function field sieve（英语：Function field sieve）
最大公因数	二进制最大公因数算法（英语：Binary GCD algorithm）辗转相除法扩展欧几里得算法 Lehmer's（英语：Lehmer's GCD algorithm）
二次剩余	Cipolla（英语：Cipolla's algorithm） Pocklington's（英语：Pocklington's algorithm） Tonelli–Shanks（英语：Tonelli–Shanks algorithm） Berlekamp（英语：Berlekamp–Rabin algorithm） Kunerth（英语：Kunerth's algorithm）
其他算法	Chakravala（英语：Chakravala method） Cornacchia（英语：Cornacchia's algorithm）整数关系（英语：Integer relation algorithm）（LLL（英语：Lenstra–Lenstra–Lovász lattice basis reduction algorithm）；KZ（英语：Korkine–Zolotarev lattice basis reduction algorithm））平方求幂整数平方根模幂运算蒙哥马利算法 Schoof（英语：Schoof's algorithm）特拉亨伯格系统（英语：Trachtenberg system）
斜体表示该算法只适用于特殊形式的数字