AKS素性测试

AKS素性测试（又被称为Agrawal–Kayal–Saxena素性测试和Cyclotomic AKS test）是一个决定型素性测试算法 ，由三个来自印度坎普尔理工学院（英语：Indian Institute of Technology Kanpur）的计算机科学家，Manindra Agrawal（英语：Manindra Agrawal）、Neeraj Kayal（英语：Neeraj Kayal）和Nitin Saxena（英语：Nitin Saxena），在2002年8月6日发表于一篇题为素数属于P的论文。作者们因此获得了许多奖项，包含了2006年的哥德尔奖和2006年的富尔克森奖。这个算法可以在多项式时间之内，决定一个给定整数是素数或者合数。

AKS最关键的重要性在于它是第一个被发表的一般的、多项式的、确定性的和无仰赖的素数判定算法。先前的算法至多达到了其中三点，但从未达到全部四个。

AKS素性测试主要是基于以下定理：整数 (≥ 2)是素数，当且仅当

${\displaystyle (x+a{)}^n\equiv <!--\; \equiv \; -->(x^n+a)(\mathrm{mod}n)}$互素的整数均成立。 这个定理是费马小定理的一般化，并且可以简单的使用二项式定理跟二项式系数的这个特征:

来证明出此定理。

虽然说关系式 (1) 基本上构成了整个素性测试，但是验证花费的时间却是指数时间。因此，为了减少计算复杂度，AKS改为使用以下的同余多项式：

${\displaystyle (x+a{)}^n\equiv <!--\; \equiv \; -->(x^n+a)(\mathrm{mod}{x}^r-<!--\; -\; -->1,n)}$与，令:

${\displaystyle (x+a{)}^n-<!--\; -\; -->(x^n+a)=(x^r-<!--\; -\; -->1)g+nf}$ = 0则 (3) 等于 (1)，因此符合必定是素数）。 然而，有一些合数也会满足这个条件式。有关AKS正确性的证明包含了推导出存在一个够小的以及一个够小的整数集合，令如果此同余式对所有里面的整数都满足，则必定为素数。

在上文引用的论文的第一版本中，作者们证明了算法的渐近时间为O${\displaystyle ({\log }^{12}<!--\; \; -->(n))}$的二进制数字长度的十二次方。但是，论文证明的时间上界却过于宽松；事实上，一个被普遍相信的关于索菲热尔曼素数分布的假设如果为真，则会立即将最坏情况减至O${\displaystyle ({\log }^6<!--\; \; -->(n))}$()是 mod 的阶。 另外，这里的 代表以二为底的对数，${\displaystyle \mathrm{\phi <!--\; \phi \; -->}(r)}$的欧拉函数。

下面说明若是个素数，那么算法总是会返回：由于是素数，步骤1和3永远不会返回。步骤5也不会返回，因为(2)对所有素数为真。因此，算法一定会在步骤4或6返回。

对应地，如果是合数，那么算法一定返回：如果算法返回，那么则一定是从步骤4或6返回。对于前者，因为 ≤ ， 必然有因子 ≤ 符合1 < gcd(,) < ，因此会返回。剩余的可能性就是步骤6，在文章中，这种情况被证明不会发生，因为在步骤5中检验的多个等式可以确保输出一定是。