AKS素性測試

AKS 素數測試是一種確定性算法，用于確定自然數在多項式時間內是否為素數。

該算法后來被其他人改進，與所有以前已知的多項式素數證明算法有顯著不同：它不建立在任何未經證實的假設（如廣義黎曼猜想）上來證明多項式運行時間——基于的長度輸入值。 原算法的漸近運行時間為 O ( ( log ? n ) 7 .5 + ε ) ，其中 n? 是要測試的數字， O? 是朗道符號，而 ε 是任意小的正數。

為了測試素數，讓數字 n >; 1? 。 此外，令 a , b , r 為自然數。

1：如果 n = a 對于 a b >; 1 返回復合；2: r = min{ r | 命令(n)> log(n) };3: 如果 1 < gcd(a,n) < n 對于某些 a ≤ r 返回 COMPOSITE；4：如果 n ≤ r 返回 PRIM；5：對于 a = 1 到 sqrt(phi(r))*log(n) do6：如果 (X+a) ? X+a ( mod (X?1), n) return COMPOSITE;7: 返回 PRIM;

該算法事實上在有限環 ( ( Z / ( n ) ) ) / ( X r ? 1 ) 有 n ? r 個元素。

考慮同余 ≡ ( mod ( X r ? 1 ) )在多項式環 Z中，將求冪 ( X + a ) n 的單項式集合減少為 { X 0 ， X 1 , … , X r ? 1 } 。 考慮同余 ≡ ( mod n ) 將所得系數的位數限制為 log ? n 。

在發現后的幾個月內，出現了新的變體，它們將 AKS 速度提高了幾個數量級。 由于存在大量變體，Crandall 和 Papadopoulos 在他們的論文 On the implementation of AKS-class primality tests（2003 年 3 月）中提到了 AKS 算法類而不是 AKS-算法。