PRIMES is in P

Solved in 2002 by Manindra Agrawal, Neeraj Kayal and Nitin Saxena.

Before 2002 primality could be tested quickly with randomized algorithms, or deterministically in polynomial time if one assumed an unproved hypothesis, but no algorithm was general, polynomial, deterministic and unconditional all at once. In August 2002 Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena at IIT Kanpur announced one. It starts from the fact that, for $a$ coprime to $n$, the polynomial identity $(X+a{)}^n\equiv X^n+a(\mathrm{mod}n)$ holds exactly when $n$ is prime, and it checks this identity modulo $X^r-1$ for a suitably small $r$ and a limited range of $a$. Their paper, PRIMES is in P, appeared in the Annals of Mathematics in 2004 and won the 2006 Gödel Prize and Fulkerson Prize. In practice faster probabilistic tests and elliptic curve methods are still used.

References

• AKS primality test (Wikipedia)
• M. Agrawal, N. Kayal, N. Saxena, PRIMES is in P (Annals of Mathematics, 2004)