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）
斜体表示该算法只适用于特殊形式的数字