AKS質數測試

AKS質數測試（又稱Agrawal–Kayal–Saxena質數測試和Cyclotomic AKS test）是一個決定型質數測試演演算法，由三個來自印度坎普爾理工學院的電腦科學家，曼寧德拉·阿格拉瓦爾、尼拉吉·卡亞爾和尼汀·沙克謝納，在2002年8月6日發表於一篇題為質數屬於P的論文。作者們因此獲得了許多獎項，包含了2006年的哥德爾獎和2006年的富爾克森獎。這個演演算法可以在多項式時間之內，決定一個給定整數是質數或者合數。

## 重要性

AKS最關鍵的重要性在於它是第一個被發表的一般的、多項式的、確定性的和無仰賴的質數判定演算法。先前的演算法至多達到了其中三點，但從未達到全部四個。

- AKS演算法可以被用於檢測任何一般的給定數字是否為質數。很多已知的高速判定演算法只適用於滿足特定條件的質數。例如，盧卡斯-萊默檢驗法僅對梅森質數適用，而Pépin測試僅對費馬數適用。
- 演算法的最長運行時間可以被表為一個目標數字長度的多項式。ECPP和APR能夠判斷一個給定數字是否為質數，但無法對所有輸入給出多項式時間範圍。
- 演算法可以確定性地判斷一個給定數字是否為質數。隨機測試演演算法，例如米勒-拉賓檢驗和Baillie–PSW，可以在多項式時間內對給定數字進行校驗，但只能給出機率性的結果。
- AKS演算法並未「仰賴」任何未證明猜想。一個反例是確定性米勒檢驗：該演算法可以在多項式時間內對所有輸入給出確定性結果，但其正確性卻基於尚未被證明的廣義黎曼猜想。

## 概念

AKS質數測試主要是基於以下定理：整數n (≥ 2)是質數，若且唯若$$(x + a)^{n} \equiv (x^{n} + a) \pmod{n}$$

這個同餘多項式對所有與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}$$ 這個多項式與存在多項式f與g，令:

$$(x + a)^n - (x^n + a) = (x^r - 1)g + nf$$ 意義是等同的。

這個同餘式可以在多項式時間之內檢查完畢。這裡我們要注意所有的質數必定滿足此條件式（令g = 0則 (3) 等於 (1)，因此符合n必定是質數）。然而，有一些合數也會滿足這個條件式。有關AKS正確性的證明包含了推導出存在一個夠小的r以及一個夠小的整數集合A，令如果此同餘式對所有A裡面的整數都滿足，則n必定為質數。

## 歷史以及運算時間

在上文引用的論文的第一版本中，作者們證明了檢驗正整數 $n$ 是否為質數的演算法時間複雜度為 $\tilde{O}(\log^{12}(n))$。但是，論文證明的時間上界較為寬鬆；事實上，一個被普遍相信的關於索菲熱爾曼質數分佈的假設如果為真，則會立即將最壞情況減至 $\tilde{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$ 卻被採用了新方法進行選擇，而正確性證明也變得更加緊緻有序。與舊證明依賴於許多不同的方法不同，新版本幾乎只依賴於有限域上的分圓多項式的特徵。新版本同時也將時間複雜度改進至 $\tilde{O}(\log^{10.5}(n))$。通過篩法獲得的其他結果可以將其進一步改進至 $\tilde{O}(\log^{7.5}(n))$。

在2005年，Carl Pomerance和H. W. Lenstra, Jr.展示了一個AKS演算法的變體，其時間複雜度為 $\tilde{O}(\log^6(n))$。

## 演演算法

整個演演算法的操作如下：

輸入：整數 n > 1

- 若存在整數a > 0 且b > 1，令 n = ab；則輸出合數
- 找出最小的 r 令 ordr(n) > log2(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)n≠ Xn+a (mod Xr − 1,n), 輸出合數。
- 輸出 質數。

這裡的 ordr(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，在文章中，這種情況被證明不會發生，因為在步驟5中檢驗的多個等式可以確保輸出一定是合數。

### 例子：n = 31為質數

輸入：整數n = 31 > 1。

1 = 若存在整數a > 0 且b > 1，令 n = ab；則輸出「合數」。

If ( a是整數 ) 輸出「合數」;

// a = n1/2...n1/4 = {5.568, 3.141, 2.360}，計算結果不是整數

2 = 找出最小的 r 令 ordr(n) > log2(n)。

nextR = True;

r = 1;

nextR = False for ( k = 1;(!nextR) &&k ≤ log2(n); k + + ){ nextR = (nk % r = = 1

nk % r = = 0);

// 計算結果為：r = 29

3 = 若 對某些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為真

4 = 若 n ≤ r, 輸出「質數」。

If ( n ≤ r ) 輸出「質數」;

// 31 > 29，計算結果n比r大

5 = 對 a = 1 到 $\scriptstyle\lfloor \scriptstyle\sqrt{\varphi(r)}\log(n) \scriptstyle\rfloor$的所有數。

如果 (X + a)n≠ Xn + a (mod Xr − 1,n), 輸出「合數」。

for ( a = 1; a ≤ $\scriptstyle\lfloor \scriptstyle\sqrt{\varphi(r)}\log(n) \scriptstyle\rfloor$, a + + )

if ( ((X + a)n-(Xn + a)) % (Xr−1,n) ≠ 0 ) 輸出「合數」。

/ * * * (x + a)31 % (x29-1,31)

= (((x + a)29 % (x29-1,31)) * (x + a)2 % 31) % (x29-1,31)

= ((1 + a29 + 29a28x + (406 % 31)a27x2 + (3654 % 31)a26x3 + (23751 % 31)a25x4 + (118755 % 31)a24x5 + (475020 % 31)a23x6 + (1560780 % 31)a22x7 + (4292145 % 31)a21x8 + (10015005 % 31)a20x9 + (20030010 % 31)a19x10 + (34597290 % 31)a18x11 + (51895935 % 31)a17x12 + (67863915 % 31)a16x13 + (77558760 % 31)a15x14 + (77558760 % 31)a14x15 + (67863915 % 31)a13x16 + (51895935 % 31)a12x17 + (34597290 % 31)a11x18 + (20030010 % 31)a10x19 + (10015005 % 31)a9x20 + (4292145 % 31)a8x21 + (1560780 % 31)a7x22 + (475020 % 31)a6x23 + (118755 % 31)a5x24 + (23751 % 31)a4x25 + (3654 % 31)a3x26 + (406 % 31)a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31)

= ((1 + a29 + 29a28x + 3a27x2 + 27a26x3 + 5a25x4 + 25a24x5 + 7a23x6 + 23a22x7 + 9a21x8 + 21a20x9 + 11a19x10 + 19a18x11 + 13a17x12 + 17a16x13 + 15a15x14 + 15a14x15 + 17a13x16 + 13a12x17 + 19a11x18 + 11a10x19 + 21a9x20 + 9a8x21 + 23a7x22 + 7a6x23 + 25a5x24 + 5a4x25 + 27a3x26 + 3a2x27 + 29ax28) * (a2 + 2ax + x2)) % (x29-1,31)

- = ((1 + 2
- 29 + 3) % 31)a2 + a31 + ((2 + 29) % 31)ax + ((29 + 2
- 1) % 31)a30x + x2 + ((3 + 2
- 29 + 1) % 31)a29x2 + ((27 + 2
- 3 + 29) % 31)a28x3 + ((5 + 2
- 27 + 3) % 31)a27x4 + ((25 + 2
- 5 + 27) % 31)a26x5 + ((7 + 2
- 25 + 5) % 31)a25x6 + ((23 + 2
- 7 + 25) % 31)a24x7 + ((9 + 2
- 23 + 7) % 31)a23x8 + ((21 + 2
- 9 + 23) % 31)a22x9 + ((11 + 2
- 21 + 9) % 31)a21x10 + ((19 + 2
- 11 + 21) % 31)a20x11 + ((13 + 2
- 19 + 11) % 31)a19x12 + ((17 + 2
- 13 + 19) % 31)a18x13 + ((15 + 2
- 17 + 13) % 31)a17x14 + ((15 + 2
- 15 + 17) % 31)a16x15 + ((17 + 2
- 15 + 15) % 31)a15x16 + ((13 + 2
- 17 + 15) % 31)a14x17 + ((19 + 2
- 13 + 17) % 31)a13x18 + ((11 + 2
- 19 + 13) % 31)a12x19 + ((21 + 2
- 11 + 19) % 31)a11x20 + ((9 + 2
- 21 + 11) % 31)a10x21 + ((23 + 2
- 9 + 21) % 31)a9x22 + ((7 + 2
- 23 + 9) % 31)a8x23 + ((25 + 2
- 7 + 23) % 31)a7x24 + ((5 + 2
- 25 + 7) % 31)a6x25 + ((27 + 2
- 5 + 25) % 31)a5x26 + ((3 + 2
- 27 + 5) % 31)a4x27 + ((29 + 2
- 3 + 27) % 31)a3x28

= a31 + x2

(x31 + a) % (x29-1,31) = a + x2

(a31 + x2)-(a + x2) = a31-a

$$\sqrt{\varphi(r)}\log_2(n) = \sqrt{28} * \log_2(31) = 26.215$$

(131-1) % 31 = 0, (231-2) % 31 = 0, (331-3) % 31 = 0, ..., (2631-26) % 31 = 0，計算結果為找不到符合的a使得(X + a)n≠ Xn + a (mod Xr − 1,n)為真

6 = 輸出「質數」。

31必為質數。

## 外部連結

- 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
- the video describes the exponential time relation (1), which it calls AKS