AKS質數測試 （又稱Agrawal–Kayal–Saxena質數測試 和Cyclotomic AKS test ）是一個決定型 質數測試 演算法 ，由三個來自印度坎普爾理工學院 曼寧德拉·阿格拉瓦爾 尼拉吉·卡亞爾 尼汀·沙克謝納 質數屬於P 的論文。[ 1] 哥德爾獎 和2006年的富尔克森奖 。這個演算法可以在多項式時間 之內，決定一個給定整數 是質數 或者合數 。
AKS最關鍵的重要性在於它是第一個被發表的一般的 、多項式的 、確定性的 和無仰賴的 質數判定算法。先前的算法至多達到了其中三點，但從未達到全部四個。
AKS質數測試主要是基於以下定理：整數n (≥ 2)是質數，若且唯若
(
x
+
a
)
n
≡
(
x
n
+
a
)
(
mod
n
)
{\displaystyle (x+a)^{n}\equiv (x^{n}+a){\pmod {n}}}
1
這個同餘 多項式對所有與n 互質 的整數a 均成立。 這個定理是費馬小定理 的一般化，並且可以簡單的使用二項式定理 跟二項式係數 的這個特徵:
(
n
k
)
≡
0
(
mod
n
)
{\displaystyle {n \choose k}\equiv 0{\pmod {n}}}
0
<
k
<
n
{\displaystyle 0<k<n}
n 是質數來證明出此定理。
雖然說關係式 (1) 基本上構成了整個質數測試，但是驗證花費的時間卻是指數時間 。因此，為了減少計算複雜度 ，AKS改為使用以下的同餘多項式：
(
x
+
a
)
n
≡
(
x
n
+
a
)
(
mod
x
r
−
1
,
n
)
{\displaystyle (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
+
n
f
{\displaystyle (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
)
)
{\displaystyle (\log ^{12}(n))}
n 的二進制 數字長度的十二次方。但是，論文證明的時間上界卻過於寬鬆；事實上，一個被普遍相信的關於索菲熱爾曼質數 分佈的假設如果為真，則會立即將最壞情況減至O
(
log
6
(
n
)
)
{\displaystyle (\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
{\displaystyle r}
有限域 上的分圓多項式的特徵。新版本同時也優化了時間複雜度的邊界到O
(
log
10.5
(
n
)
)
{\displaystyle (\log ^{10.5}(n))}
篩法 獲得的其他結果可以將其進一步簡化到O
(
log
7.5
(
n
)
)
{\displaystyle (\log ^{7.5}(n))}
在2005年，Carl Pomerance 和H. W. Lenstra, Jr. 展示了一個AKS的變體，可以在
O
(
log
6
(
n
)
)
{\displaystyle O(\log ^{6}(n))}
n
{\displaystyle n}
O
(
log
12
(
n
)
)
{\displaystyle O(\log ^{12}(n))}
[ 2]
整個演算法的操作如下：[ 1]
輸入：整數 n > 1 若存在整數a > 0 且b > 1 ，令 n = a b 合數
找出最小的 r 令 ord r n ) > log2 (n ).
若 對某些a ≤ r ，1 < gcd(a ,n ) < n ，輸出合數 。(gcd是指最大公因數 )。
若 n ≤ r , 輸出質數 。
對 a = 1 到
⌊
φ
(
r
)
log
(
n
)
⌋
{\displaystyle \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor }
如果 (X +a )n X n a (mod X r n ), 輸出合數 。
輸出 質數 。 這裡的 ord r n )是n mod r 的阶。 另外，這裡的log 代表以二為底的對數，
φ
(
r
)
{\displaystyle \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] 合數 。
n = 31為質數輸入：整數n = 31 > 1。
若存在整數a > 0 且b > 1 ，令 n = a b 2 (n); b + + ){
a = n1/b ;
If ( a是整數 ) 輸出「合數」;
}
// a = n1/2 ...n1/4 = {5.568, 3.141, 2.360}，計算結果不是整數
找出最小的 r 令 ord r n ) > log2 (n )。
nextR = True;
r = 1;
while ( nextR = = True ) {
r + + ;
nextR = False
for ( k = 1;(!nextR) &&k ≤ log2 (n); k + + ){
nextR = (nk % r = = 1 || nk % 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 到
⌊
φ
(
r
)
log
(
n
)
⌋
{\displaystyle \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor }
X + a )n X n a (mod X r n ), 輸出「合數」。
for ( a = 1; a ≤
⌊
φ
(
r
)
log
(
n
)
⌋
{\displaystyle \scriptstyle \lfloor \scriptstyle {\sqrt {\varphi (r)}}\log(n)\scriptstyle \rfloor }
X + a )n X n a )) % (X r n ) ≠ 0 ) 輸出「合數」。
}
/ * * *
(x + a)31 % (x29 -1,31)
= (((x + a)29 % (x29 -1,31)) * (x + a)2 % 31) % (x29 -1,31)
= ((1 + a29 + 29a28 x + (406 % 31)a27 x2 + (3654 % 31)a26 x3 + (23751 % 31)a25 x4 + (118755 % 31)a24 x5 + (475020 % 31)a23 x6 + (1560780 % 31)a22 x7 + (4292145 % 31)a21 x8 + (10015005 % 31)a20 x9 + (20030010 % 31)a19 x10 + (34597290 % 31)a18 x11 + (51895935 % 31)a17 x12 + (67863915 % 31)a16 x13 + (77558760 % 31)a15 x14 + (77558760 % 31)a14 x15 + (67863915 % 31)a13 x16 + (51895935 % 31)a12 x17 + (34597290 % 31)a11 x18 + (20030010 % 31)a10 x19 + (10015005 % 31)a9 x20 + (4292145 % 31)a8 x21 + (1560780 % 31)a7 x22 + (475020 % 31)a6 x23 + (118755 % 31)a5 x24 + (23751 % 31)a4 x25 + (3654 % 31)a3 x26 + (406 % 31)a2 x27 + 29ax28 ) * (a2 + 2ax + x2 )) % (x29 -1,31)
= ((1 + a29 + 29a28 x + 3a27 x2 + 27a26 x3 + 5a25 x4 + 25a24 x5 + 7a23 x6 + 23a22 x7 + 9a21 x8 + 21a20 x9 + 11a19 x10 + 19a18 x11 + 13a17 x12 + 17a16 x13 + 15a15 x14 + 15a14 x15 + 17a13 x16 + 13a12 x17 + 19a11 x18 + 11a10 x19 + 21a9 x20 + 9a8 x21 + 23a7 x22 + 7a6 x23 + 25a5 x24 + 5a4 x25 + 27a3 x26 + 3a2 x27 + 29ax28 ) * (a2 + 2ax + x2 )) % (x29 -1,31)
= ((1 + 2 * 29 + 3) % 31)a2 + a31 + ((2 + 29) % 31)ax + ((29 + 2 * 1) % 31)a30 x + x2 + ((3 + 2 * 29 + 1) % 31)a29 x2 + ((27 + 2 * 3 + 29) % 31)a28 x3 + ((5 + 2 * 27 + 3) % 31)a27 x4 + ((25 + 2 * 5 + 27) % 31)a26 x5 + ((7 + 2 * 25 + 5) % 31)a25 x6 + ((23 + 2 * 7 + 25) % 31)a24 x7 + ((9 + 2 * 23 + 7) % 31)a23 x8 + ((21 + 2 * 9 + 23) % 31)a22 x9 + ((11 + 2 * 21 + 9) % 31)a21 x10 + ((19 + 2 * 11 + 21) % 31)a20 x11 + ((13 + 2 * 19 + 11) % 31)a19 x12 + ((17 + 2 * 13 + 19) % 31)a18 x13 + ((15 + 2 * 17 + 13) % 31)a17 x14 + ((15 + 2 * 15 + 17) % 31)a16 x15 + ((17 + 2 * 15 + 15) % 31)a15 x16 + ((13 + 2 * 17 + 15) % 31)a14 x17 + ((19 + 2 * 13 + 17) % 31)a13 x18 + ((11 + 2 * 19 + 13) % 31)a12 x19 + ((21 + 2 * 11 + 19) % 31)a11 x20 + ((9 + 2 * 21 + 11) % 31)a10 x21 + ((23 + 2 * 9 + 21) % 31)a9 x22 + ((7 + 2 * 23 + 9) % 31)a8 x23 + ((25 + 2 * 7 + 23) % 31)a7 x24 + ((5 + 2 * 25 + 7) % 31)a6 x25 + ((27 + 2 * 5 + 25) % 31)a5 x26 + ((3 + 2 * 27 + 5) % 31)a4 x27 + ((29 + 2 * 3 + 27) % 31)a3 x28
= a31 + x2
(x31 + a) % (x29 -1,31) = a + x2
(a31 + x2 )-(a + x2 ) = a31 -a
φ
(
r
)
log
2
(
n
)
=
28
∗
log
2
(
31
)
=
26.215
{\displaystyle {\sqrt {\varphi (r)}}\log _{2}(n)={\sqrt {28}}*\log _{2}(31)=26.215}
31 -1) % 31 = 0, (231 -2) % 31 = 0, (331 -3) % 31 = 0, ..., (2631 -26) % 31 = 0，計算結果為找不到符合的a 使得(X + a )n X n a (mod X r n )為真
* * * /
