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) 是質數，若且唯若

　
:

這個同餘多項式對所有與 _n_ 互質的整數 _a_ 均成立。 這個定理是費馬小定理的一般化，並且可以簡單的使用二項式定理跟二項式係數的這個特徵:

　
: ${n \choose k}\equiv 0{\pmod {n}}$ ，對任何 $0<k<n$ ，若且唯若 _n_ 是質數

來證明出此定理。

雖然說關係式 (1) 基本上構成了整個質數測試，但是驗證花費的時間卻是指數時間。因此，為了減少計算複雜度，AKS 改為使用以下的同餘多項式：

　
:

這個多項式與存在多項式 _f_ 與 _g_，令:

　
:

意義是等同的。

這個同餘式可以在多項式時間之內檢查完畢。這裡我們要注意所有的質數必定滿足此條件式（令 _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))$ 邊界而言，這是一個顯著的改進。

## 演算法

整個演算法的操作如下：

　
: 輸入：整數 _n_ > 1

1. 若存在整數 _a_> 0 且 _b_> 1 ，令 _n_ = _a_b ；則輸出_合數_
2. 找出最小的 _r_ 令 _ord_r(_n_) > log2(_n_).
3. 若 對某些 _a_ ≤ _r_，1 < gcd(_a_,_n_) < _n_，輸出_合數_。(gcd 是指最大公因數)。
4. 若 _n_ ≤ _r_, 輸出_質數_。
5. 對 _a_= 1 到 $\scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor $ 的所有數，

　
: 如果 (_X_+_a_)n≠ _X_n+_a_ (mod _X_r − 1,_n_), 輸出_合數_。
6. 輸出 _質數_。

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

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

　
: 輸入：整數 _n_  =  31 > 1。

## 註釋

## 延伸閱讀

## 外部連結

* 埃里克・韋斯坦因. 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]