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）
斜體表示該演算法只適用於特殊形式的數字