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]