AKS primality test

The AKS primality test (Agrawal-Kayal-Saxena, 2002) is the first deterministic algorithm to test whether a number is prime in polynomial time — specifically, O((log n)^12), later improved to O((log n)^6). Unlike probabilistic tests such as the Miller-Rabin test, AKS requires no randomness and never errs: it definitively answers prime or composite. The result resolved a centuries-old question and proved that primality testing is in P, a striking asymmetry given that the related problem of factorization remains outside P.

The algorithm exploits a generalization of Fermat's Little Theorem to polynomial rings over finite fields. Its practical significance is limited — probabilistic tests remain faster for all realistic key sizes — but its theoretical importance is profound. AKS demonstrates that a problem once believed to require randomness or heuristics admits a clean, deterministic polynomial solution.

The AKS test is a monument to theoretical elegance over practical necessity. That it was developed not in a major research center but by three computer scientists at the Indian Institute of Technology Kanpur is itself a rebuke to the concentration of scientific capacity in wealthy institutions — and a reminder that the most consequential mathematical breakthroughs emerge from unexpected places.