The algorithm that finally solved the ancient mystery of prime numbers

The algorithm that finally solved the ancient mystery of prime numbers
Image: Intellect (generated)

In short: For centuries, mathematicians struggled to find a perfect way to identify prime numbers. They could find them quickly, but they couldn't be certain. In 2002, three computer scientists changed everything by discovering a method that is simultaneously general, deterministic, and unconditionally correct.

Before the AKS primality test, algorithms faced a fundamental trade-off. You could have speed, but you had to accept a probabilistic result, like the Miller–Rabin test. Or, you could have certainty, but the method might only work for specific types of numbers, such as Mersenne or Fermat numbers. Even the deterministic Miller's version of the Miller–Rabin test relies on the unproved generalized Riemann hypothesis to guarantee correctness.

On August 6, 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena from the Indian Institute of Technology Kanpur published "PRIMES is in P". Their breakthrough was the first algorithm to be general, polynomial-time, deterministic, and unconditionally correct without relying on unproved mathematical conjectures or the field of analysis. This achievement earned them the Gödel Prize and the Fulkerson Prize in 2006.

Despite its theoretical brilliance, the AKS algorithm is often called a "galactic algorithm." This means that while it is mathematically perfect, it is rarely used in practical computing. For 64-bit inputs, the Baillie–PSW test is much faster. For larger numbers, methods like ECPP or APR are superior because they can produce a primality certificate for rapid independent verification—something the AKS algorithm cannot do.

The algorithm's complexity has been refined significantly since its inception. The original version had a loose upper bound of O(log(n)^12), but subsequent research and variants have pushed that complexity down. While a variant proposed by the authors could theoretically run in O(log(n)^3), the algorithm remains a monumental achievement in number theory.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-aks-primality-test.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…