AKS primality test

Background

Whether primality can be tested deterministically in polynomial time was a long-standing open problem. Earlier fast tests were either randomised or relied on the unproven generalised Riemann hypothesis. At IIT Kanpur, Professor Manindra Agrawal and his undergraduate students Neeraj Kayal and Nitin Saxena found a short, elementary proof based on a generalisation of Fermat's little theorem.

Significance

Settled a classic question of mathematics and computer science, and won the 2006 Gödel Prize and Fulkerson Prize. It was achieved entirely in India, with two undergraduates as co-authors.

Meanwhile in the West

Solved a long-open problem in theoretical computer science.

Fair to say

Practical cryptography still uses faster probabilistic tests; AKS is a theoretical landmark.

Path to modern innovation

A landmark in complexity theory.

Global impact

• New research on derandomisation and polynomial identity testing.

Transmission

Done entirely in India.

Primary sources

• 1Agrawal, Kayal & Saxena, PRIMES is in P (Annals of Mathematics, 2004)

Further reading

• 2Wikipedia: Agrawal–Kayal–Saxena primality test