View source for 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 versus NP|P]]''', a striking asymmetry given that the related problem of factorization remains outside '''[[P versus NP|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.''

[[Category:Mathematics]] [[Category:Computer Science]]