AKS primality test

Lore & Background

The AKS primality test is based on a theorem generalizing Fermat's little theorem to polynomials. It uses the polynomial congruence relation (X + a)^n ≡ X^n + a (mod n) in the ring (Z/nZ)[X]/(X^r - 1). The algorithm evaluates this congruence for a large set of a values, with r and the set size polynomial in the digits of n. The proof shows that if the congruences hold, then n is a power of a prime.

Reader's Guide

The AKS primality test is of immense theoretical importance as the first algorithm to be simultaneously general, polynomial-time, deterministic, and unconditionally correct. Previous algorithms achieved at most three of these four properties. For example, the Lucas–Lehmer test works only for Mersenne numbers, and Miller's test depends on the generalized Riemann hypothesis. However, AKS is not used in practice, rendering it a galactic algorithm. For 64-bit inputs, the Baillie–PSW test is deterministic and runs many orders of magnitude faster. For larger inputs, ECPP and APR tests are far superior, and ECPP can output a primality certificate for independent verification, which AKS cannot. The original paper had asymptotic time complexity O~(log(n)^12), later improved by variants. In 2006 the authors received both the Gödel Prize and Fulkerson Prize for their work.

Did You Know?

• The AKS algorithm was the first primality-proving algorithm to be simultaneously general, polynomial-time, deterministic, and unconditionally correct.
• The algorithm's correctness does not rely on any subsidiary unproved hypothesis, unlike Miller's test which depends on the generalized Riemann hypothesis.
• The AKS algorithm is not used in practice; for 64-bit inputs, the Baillie–PSW test is many orders of magnitude faster.

The Breakthrough at Kanpur

In August 2002, three computer scientists at the Indian Institute of Technology Kanpur—Manindra Agrawal, Neeraj Kayal, and Nitin Saxena—published a paper whose title was simply "PRIMES is in P." That deceptively short declaration announced a result that had eluded mathematicians and computer scientists for generations: a deterministic algorithm that decides whether an arbitrary integer is prime or composite in polynomial time, with no dependence on unproved conjectures. The work also stood apart from earlier approaches because its proof drew entirely on algebraic and number-theoretic tools, deliberately avoiding the field of mathematical analysis. The algorithm quickly acquired several names—the Agrawal–Kayal–Saxena test, the cyclotomic AKS test—but the initials AKS became the standard shorthand. Four years later, in 2006, the trio's contribution was recognized with both the Gödel Prize and the Fulkerson Prize, cementing the result's standing as one of the landmark achievements in theoretical computer science.

The Four-Property Milestone

For centuries, primality-testing methods had managed to satisfy at most three of four desirable criteria: generality (working on any integer), polynomial running time, determinism (giving a definitive yes-or-no answer), and unconditional correctness (not resting on unproved hypotheses). AKS was the first algorithm to check all four boxes simultaneously. Earlier specialized tests such as Lucas–Lehmer and Pépin's test were fast and deterministic but applied only to Mersenne and Fermat numbers, respectively. The ECPP and APR-CL methods could prove primality for arbitrary inputs without conjectural assumptions, yet no polynomial-time bound was known for every possible input. Randomized procedures like Miller–Rabin and Baillie–PSW ran in polynomial time on any number, but their verdicts carried a nonzero error probability. Miller's deterministic variant of Miller–Rabin achieved polynomial time and certainty, but only under the unproved generalized Riemann hypothesis. AKS sidestepped every one of these compromises, delivering a single, unconditional, worst-case polynomial guarantee for every integer at or above two.

The Algebraic Heart

At its core, AKS rests on a polynomial congruence that generalizes Fermat's little theorem from integers to the ring of polynomials with coefficients taken modulo n. For a candidate integer n ≥ 2 and a base a coprime to n, the test asserts that n is prime if and only if a particular polynomial identity holds inside the quotient ring (Z/nZ)[X]/(X^r − 1). One direction of the equivalence follows almost immediately from the binomial theorem together with the classical fact that every binomial coefficient C(n,k) is divisible by n when n is prime and 0 < k < n. The difficulty lies in the reverse direction and in making the computation tractable. A naïve expansion of (X + a)^n would produce n + 1 coefficients to reduce modulo n, an exponential task. The key engineering insight is to work in the quotient ring where X^r is identified with 1, thereby capping the degree of every polynomial that appears. The running time then depends on the size of the auxiliary parameter r rather than on n itself, which is what makes the overall procedure polynomial in the number of digits of the input.

Theory Versus Practice

Despite its celebrated place in the history of algorithms, AKS is what practitioners call a galactic algorithm: its worst-case polynomial bound is so large in practice that no real-world system relies on it. For 64-bit integers, the Baillie–PSW test is deterministic and executes many orders of magnitude faster. For much larger inputs, the unconditionally correct ECPP and APR-CL methods outperform AKS by a wide margin, and ECPP additionally produces a primality certificate that a third party can verify independently and quickly—a capability AKS does not offer. In other words, the algorithm's contribution is almost entirely conceptual. It settled a long-standing question in complexity theory by proving that the language of primes belongs to the class P, a result that reshaped how researchers think about the boundary between polynomial-time and exponential-time computation. The Gödel and Fulkerson Prizes awarded in 2006 acknowledged precisely this theoretical significance, even as the algorithm itself remained a monument rather than a tool.