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-算法。