The AKS primality test (also known as the Agrawal–Kayal–Saxena primality test and the cyclotomic AKS test) is a deterministic primality-proving algorithm created and published by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena, computer scientists at the Indian Institute of Technology Kanpur, on August 6, 2002, in an article titled "PRIMES is in P". The algorithm was the first one which is able to determine in polynomial time, whether a given number is prime or composite without relying on mathematical conjectures such as the generalized Riemann hypothesis. The proof is also notable for not relying on the field of analysis. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

AKS is the first primality-proving algorithm to be simultaneously general, polynomial-time, deterministic, and unconditionally correct. Previous algorithms had been developed for centuries and achieved three of these properties at most, but not all four.

While the algorithm is of immense theoretical importance, it is not used in practice, rendering it a galactic algorithm. For 64-bit inputs, the Baillie–PSW test is deterministic and runs many orders of magnitude faster. For larger inputs, the performance of the (also unconditionally correct) ECPP and APR tests is far superior to AKS. Additionally, ECPP can output a primality certificate that allows independent and rapid verification of the results, which is not possible with the AKS algorithm.

The AKS primality test is based upon the following theorem: Given an integer ${\displaystyle n\geq 2}$ and integer ${\displaystyle a}$ coprime to ${\displaystyle n}$, ${\displaystyle n}$ is prime if and only if the polynomial congruence relation

holds within the polynomial ring ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$. Note that ${\displaystyle X}$ denotes the indeterminate which generates this polynomial ring.

This theorem is a generalization to polynomials of Fermat's little theorem. In one direction it can easily be proven using the binomial theorem together with the following property of the binomial coefficient:

While the relation (1) constitutes a primality test in itself, verifying it takes exponential time: the brute force approach would require the expansion of the ${\displaystyle (X+a)^{n}}$ polynomial and a reduction ${\displaystyle {\pmod {n}}}$ of the resulting ${\displaystyle n+1}$ coefficients.

The congruence is an equality in the polynomial ring ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$. Evaluating in a quotient ring of ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]}$ creates an upper bound for the degree of the polynomials involved. The AKS evaluates the equality in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )[X]/(X^{r}-1)}$, making the computational complexity dependent on the size of ${\displaystyle r}$. For clarity, this is expressed as the congruence