AKS Primality Test

Purpose: Decide primality in deterministic polynomial time, with no randomness and no unproven hypotheses. Agrawal-Kayal-Saxena, 2002 — the paper that finally put PRIMES in P.

The Idea

Everything rests on a polynomial identity. For $\gcd (a,n)=1$:

$n\text{ is prime}⟺(x+a{)}^n\equiv x^n+a(\mathrm{mod}n).$

The forward direction is the freshman’s dream, valid mod a prime because every binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ for $0<k<n$ is divisible by $n$. Checking this identity directly costs $O(n)$ coefficients — far too many. AKS’s contribution is showing it suffices to check it modulo a small polynomial $x^r-1$, for a suitably chosen small $r$, and for a bounded range of $a$.

Algorithm

1. If $n=m^k$ for some $k>1$, output composite.
2. Find the smallest $r$ such that ${\mathrm{ord}}_r(n)>{\log }^{2}n$.
3. For $a\le r$: if $1<\gcd (a,n)<n$, output composite.
4. If $n\le r$, output prime.
5. For $a=1\dots \lfloor \sqrt{\phi (r)}\log n\rfloor$: if
   $(x+a{)}^n\not\equiv x^n+a(\mathrm{mod}{x}^r-1,n),$
   output composite.
6. Output prime.

Complexity

• Original paper: $\tilde{O}({\log }^{12}n)$
• With Lenstra-Pomerance improvements: $\tilde{O}({\log }^{6}n)$
• Space: polynomial

Why nobody uses it

${\log }^{6}n$ with a large hidden constant is astronomically slower than Miller-Rabin for every input anyone will ever test. For 64-bit numbers, deterministic Miller-Rabin with 12 fixed bases finishes in under a microsecond; AKS takes seconds. For cryptographic sizes, ECPP produces a certificate far faster.

Test	Time	Deterministic?	Practical?
Trial division	$O(\sqrt{n})$	yes	only for tiny $n$
Miller-Rabin, fixed bases	$O(k{\log }^{3}n)$	yes for 64-bit	yes
Miller-Rabin, random bases	$O(k{\log }^{3}n)$	no ($4^{-k}$ error)	yes
Baillie-PSW	$O({\log }^{3}n)$	no counterexample known	yes
ECPP	heuristic $\tilde{O}({\log }^{4}n)$	yes, with certificate	yes, for huge $n$
AKS	$\tilde{O}({\log }^{6}n)$	yes	no

Why it still matters

AKS resolved a decades-old open question: primality testing is in P, unconditionally. Before it, deterministic polynomial-time primality was known only under the generalised Riemann hypothesis (Miller’s original result). It is a landmark in complexity theory even though it is a footnote in practice — a good reminder that “polynomial time” and “fast” are different claims.

Variants / Use Cases

• Miller-Rabin — what you should actually write
• Lucas-Lehmer — specialised deterministic test for Mersenne numbers
• Primality Testing — the topic page comparing all of these
• Complexity Theory — where PRIMES ∈ P sits in the landscape