Deterministic Primality: the AKS Test
By 2002 the question "is n prime?" was, in practice, completely solved:
the Miller–Rabin test
settles it for a thousand-digit number in milliseconds, and has never once let a serious composite
through. But it is randomised — it flips coins and reports "prime with astronomically high
probability". A stubborn theoretical question remained open for decades: could a computer decide
primality with no randomness, no unproven hypothesis, and a
guaranteed polynomial-time running time? Was \text{PRIMES}
in the complexity class \mathsf{P}?
In August 2002, three researchers at IIT Kanpur — Manindra Agrawal and his students
Neeraj Kayal and Nitin Saxena — answered yes, in a paper
of barely nine pages titled simply "PRIMES is in P". It was an instant sensation: an unconditional,
deterministic, polynomial-time primality test, resting on nothing deeper than a clever twist of a
fact a school student can state. This page tells that story and takes the AKS algorithm apart.
The state of the art before AKS
Primality had been squeezed into ever-tighter theoretical boxes for thirty years, from every
direction except the one that mattered. Reading the table below, remember what each
qualifier costs: "randomised" spends coin-flips, "under GRH" spends an unproven hypothesis, and a
complexity class like \mathsf{co\text{-}NP} only promises a short
certificate, not a fast algorithm.
| Result | Who / when | What it gave | The catch |
|---|
| Trial division | antiquity |
a deterministic, correct test |
exponential time — \sqrt n divisions |
| Pratt certificates | Pratt, 1975 |
\text{PRIMES}\in\mathsf{NP} — a short proof of primality exists |
a certificate, not an algorithm to find it fast |
| Compositeness witnesses | — |
\text{PRIMES}\in\mathsf{co\text{-}NP} (a factor witnesses "composite") |
same — existence of a certificate only |
| Miller's test | Miller, 1976 |
deterministic polynomial time |
correct only if the GRH holds (unproven) |
| Solovay–Strassen, Miller–Rabin | 1977, 1980 |
\text{PRIMES}\in\mathsf{RP} / randomised poly-time |
randomised — a (tiny) error probability |
| Adleman–Pomerance–Rumely | 1983 |
deterministic, unconditional |
time (\log n)^{O(\log\log\log n)} — almost, not quite, polynomial |
| AKS | 2002 |
\text{PRIMES}\in\mathsf{P} — deterministic, unconditional, polynomial |
none — but slow in practice |
AKS filled the one empty cell that had resisted everyone: deterministic and
unconditional and polynomial, all three at once.
The seed: a polynomial Freshman's Dream
Everything grows from one identity. Beginners are often told the "Freshman's Dream" is
wrong — (x+a)^n \ne x^n + a^n in general. But work modulo a prime
and a version of the dream comes true. The whole of AKS is built on this characterisation of primes.
Let a be an integer with \gcd(a,n)=1 and
n\ge 2. Then:
- n is prime if and only if the polynomial congruence
(x+a)^n \equiv x^n + a \pmod{n} holds — meaning
every coefficient agrees mod n;
- the reason is that the binomial coefficient
\binom{n}{k} is divisible by n for all
0 < k < n exactly when n is prime.
Why does the coefficient divisibility do it? Expand
(x+a)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}x^k. The two end terms are
x^n (from k=n) and
a^n (from k=0); by
Fermat's Little
Theorem, a^n\equiv a when n is
prime. Every middle term carries a factor \binom{n}{k}, and for a
prime those are all \equiv 0 \pmod n — so the middle collapses and we are
left with x^n + a. If n is composite, at least
one middle coefficient survives, and the identity fails. A perfect primality test!
Worked example: n=3 versus n=4
Take a=1 and watch the identity separate a prime from a composite.
The prime n=3. Expand
(x+1)^3 = x^3 + 3x^2 + 3x + 1. The middle coefficients are
\binom{3}{1}=\binom{3}{2}=3\equiv 0 \pmod 3, so modulo
3:
(x+1)^3 \equiv x^3 + 1 \pmod 3.
The middle vanished — the identity holds, correctly declaring 3
prime.
The composite n=4. Expand
(x+1)^4 = x^4 + 4x^3 + 6x^2 + 4x + 1. Now the middle coefficient
\binom{4}{2}=6\equiv 2 \pmod 4 does not vanish:
(x+1)^4 \equiv x^4 + 2x^2 + 1 \not\equiv x^4 + 1 \pmod 4.
The stubborn 2x^2 term is a watertight certificate that
4 is composite. That surviving coefficient — 6
is not a multiple of 4 because 4=2\cdot 2 shares
the factor 2 with \binom 4 2 — is exactly where
compositeness leaves its fingerprint.
The problem — and the fix that made it polynomial
The identity is beautiful, but as an algorithm it is hopeless. Expanding
(x+a)^n produces a polynomial with n+1
coefficients — for a thousand-digit n that is more terms than there are
atoms in the universe. Checking them all is exponential in the number of digits, exactly
what we are trying to avoid.
The AKS masterstroke is to compute the same congruence in a small quotient ring.
Instead of full polynomials, work modulo x^r - 1 for a cleverly chosen
small r. That is, the test becomes: does
(x+a)^n \equiv x^n + a \pmod{\,n,\ x^r - 1\,}\quad\text{in the ring } (\mathbb{Z}/n\mathbb{Z})[x]\big/(x^r-1)?
Reducing mod x^r-1 means every time a power x^m
appears you replace it by x^{m \bmod r} — because
x^r \equiv 1 in this ring. Now there are only r
coefficients to track, not n+1. With
r polynomial in \log n, and the powering done by
fast
exponentiation (repeated squaring), the whole check runs in polynomial time.
- If n is a perfect power a^b\ (b>1), it is composite — reject.
- Find the smallest r such that the multiplicative order of
n modulo r exceeds
(\log n)^2.
- Check \gcd(a,n)=1 for all a\le r; a proper factor found means composite.
- For every a from 1 up to about
\sqrt{r}\,\log n, verify
(x+a)^n \equiv x^n + a \pmod{n,\;x^r-1}. If any fails,
n is composite.
- If all pass, n is prime — with certainty.
Why the shortcut is still correct: introspection
Shrinking the ring is a genuine gamble: composites that fail the full identity might sneak
through the reduced congruence for a single a. AKS closes the gap by
testing a whole range of values a=1,2,\dots,\lfloor\sqrt r\,\log n\rfloor
— and the heart of the proof is a counting argument about which numbers are
"introspective".
A number m is called introspective for a polynomial
f(x) when f(x)^m \equiv f(x^m) \pmod{n,\;x^r-1}.
The passing congruences make each base polynomial x+a introspective for
both n and (trivially) for the prime p dividing
n. Introspection is closed under products, so from the
a-range you generate a large multiplicative group of introspective numbers
and a large group of polynomials. Counting the same group two ways then forces the algebra to be
consistent only if n is a power of p — and the
first step already ruled out perfect powers. So n=p: prime. That squeeze
between two group-size bounds is the entire correctness proof in one breath.
The deep number theory hidden in "choose a small r"
The one step that reaches into analytic number theory is finding a small
r for which n has large multiplicative order.
AKS need to guarantee such an r with
r = O((\log n)^5), and to do it they lean on a sieve-theoretic estimate on
the density of primes q whose largest prime factor of
q-1 is large — a distribution closely tied to
Sophie Germain primes (primes q with
2q+1 also prime). The original paper used a result of Fouvry; a cleaner
bound comes from a lemma about the product of the first few primes:
\operatorname{lcm}(1,2,\dots,m)\ \ge\ 2^{m-1},
which guarantees a suitable r \le \lceil(\log n)^5\rceil exists. This is
the point where the elementary algebra borrows muscle from the distribution of primes — the
beating heart of analytic number theory — to keep r, and therefore the
running time, small.
The complexity, and how it shrank
The dominant cost is the loop: about \sqrt r\,\log n values of
a, each requiring a modular exponentiation of a degree-r
polynomial with coefficients mod n. Bookkeeping the bit operations gives the
original headline figure and its later improvement:
- As published in 2002, using r=O((\log n)^5), the running time is
\tilde{O}\big((\log n)^{12}\big).
- Under a Lenstra–Pomerance refinement (a modified r via a different
sieve/analytic input), this drops to
\tilde{O}\big((\log n)^{6}\big).
The \tilde O ("soft-O") hides factors of
\log\log n and the like. Either way the exponent is a fixed constant, so
the running time is a polynomial in the input length \log n — which
is precisely the statement \text{PRIMES}\in\mathsf{P}. That the exponent
fell from 12 to 6 within a couple of years, again
by feeding in sharper prime-distribution estimates, shows how tightly the algorithm's speed is bolted
to analytic number theory.
The polynomial congruence, in code
The reduced congruence is deceptively simple to state as a computation. Here is the shape of the
inner check — powering x+a by repeated squaring, always reducing modulo
both n and x^r-1. (A fragment for intuition, not
a production routine.)
// Polynomials are length-r coefficient arrays: index i holds the coeff of x^i.
// Multiplication reduces x^m -> x^(m mod r) automatically (mod x^r - 1),
// and every coefficient is kept in the range 0..n-1 (mod n).
function mulModCyclotomic(p: number[], q: number[], r: number, n: number): number[] {
const out = new Array<number>(r).fill(0);
for (let i = 0; i < r; i++) {
if (p[i] === 0) continue;
for (let j = 0; j < r; j++) {
const k = (i + j) % r; // x^(i+j) folds back via x^r = 1
out[k] = (out[k] + p[i] * q[j]) % n; // coefficients live mod n
}
}
return out;
}
// Does (x + a)^n === x^n + a in (Z/nZ)[x] / (x^r - 1) ?
function aksCongruenceHolds(a: number, n: number, r: number): boolean {
let result = [1]; // the polynomial "1"
let base = [a % n, 1]; // the polynomial (x + a)
let e = n;
while (e > 0) { // fast exponentiation, O(log n) squarings
if (e & 1) result = mulModCyclotomic(result, base, r, n);
base = mulModCyclotomic(base, base, r, n);
e = Math.floor(e / 2);
}
// Build the target x^n + a reduced mod (n, x^r - 1):
const target = new Array<number>(r).fill(0);
target[n % r] = (target[n % r] + 1) % n; // the x^n term folds to x^(n mod r)
target[0] = (target[0] + a) % n; // the constant a
return result.every((c, i) => c === target[i]);
}
AKS is a monument of theory: it settled \text{PRIMES}\in\mathsf{P},
a decades-old open question, with an elementary and self-contained proof. But do not reach for it to
test a real number. Even at \tilde O((\log n)^6) it is
orders of magnitude slower than the tools people actually use:
Miller–Rabin
(randomised, blazing fast, error you can drive below cosmic-ray levels) for everyday work, and
ECPP
(elliptic-curve primality proving) when you need a rigorous certificate for a very large
prime. AKS wins the theorem; those two win the race.
And a technical trap: the congruence (x+a)^n\equiv x^n+a must be checked
in the quotient ring modulo x^r-1, not as full
polynomials. Skip the reduction and you are back to n+1 coefficients and
exponential time — the reduction mod x^r-1 is the entire reason
the algorithm is polynomial, not an optional optimisation.
The AKS paper, "PRIMES is in P", ran to about nine pages and used no machinery heavier than
undergraduate algebra and a sprinkle of analytic number theory. Two of its three authors, Kayal and
Saxena, were undergraduate students of Agrawal at the time. Word spread by email within days
of the August 2002 preprint; within weeks it had been checked, re-checked, and celebrated worldwide.
It won the 2006 Gödel Prize and the Fulkerson Prize. The moral that thrilled the community: a
genuinely fundamental question — one that Gauss himself flagged as "deserving the utmost care" — could
still fall to an elementary idea, a Freshman's Dream examined closely enough.
It is tempting to hope that checking the reduced congruence for a single well-chosen
a suffices. It does not: individual composites can pass the reduced test
for particular a by coincidence, just as pseudoprimes fool a single-base
Fermat test. The correctness proof genuinely needs the whole range up to
\sqrt r\,\log n: only then is the group of introspective numbers large
enough for the two-way counting argument to pin n down to a prime power.
The range is not padding — it is load-bearing.