Engineering / Mathematics — Primality Testing
The AKS Algorithm and Its Analysis
The AKS algorithm in full, its correctness argument, complexity, and why it is not used in practice.
Executive summary
AKS assembles a perfect power check, a search for a suitable modulus r, a gcd sweep, and a bounded set of polynomial congruence checks into a deterministic polynomial-time primality test.
Its complexity is polynomial but of high degree, which is why every practical system still uses Miller-Rabin.
Learning objectives
- State the algorithm's steps in order.
- Sketch the correctness argument.
- Compare its complexity against the probabilistic alternative.
01The algorithm
AKS primality test
integer n > 1prime or composite, with certainty- If n is a perfect power, report composite.
- Find the smallest r such that the multiplicative order of n modulo r exceeds (log₂ n)².
- For each a ≤ r: if 1 < gcd(a, n) < n, report composite.
- If n ≤ r, report prime.
- For each a from 1 to a bound derived from r and n:
- If (X + a)^n ≢ X^n + a (mod n, X^r − 1), report composite.
- Report prime.
polynomial in log n; originally about (log n)^{12}, later improvedEach polynomial congruence is checked by repeated squaring in the quotient ring, so the cost is a number of polynomial multiplications proportional to log n, each on polynomials of degree below r.
02Correctness in outline
Perfect powers removed
Step 1 eliminates the case that would otherwise pass for structural reasons.
Small factors removed
Step 3 catches any n sharing a factor with some a ≤ r.
Suppose n is composite and passes
Then a certain group of residues generated by the checked congruences must be large.
Derive a contradiction
Counting the distinct polynomials the group generates exceeds the size the quotient ring permits.
The existence of a suitable r below a polynomial bound is itself a non-trivial number-theoretic estimate, and it is what keeps the polynomial degree — and hence the cost of each multiplication — under control.
03Why Miller-Rabin still wins
- Miller-Rabin, 40 rounds
O(len(n)³) × 40Error below 2^{−80}; milliseconds at 2048 bits - AKS, original
Õ(len(n)^{12})Deterministic; impractical at cryptographic sizes - AKS, improved variants
Õ(len(n)^{6})Still far slower than the probabilistic test - Elliptic curve primality proving
Heuristically Õ(len(n)^{4})The practical choice when a certificate is required
| Requirement | Method |
|---|---|
| Fast test, error below hardware fault rate | Miller-Rabin |
| Verifiable certificate of primality | Elliptic curve primality proving |
| Unconditional deterministic guarantee | AKS |
| Small inputs | Trial division against a sieved table |
The practical lesson generalises beyond this case: a polynomial-time algorithm is not automatically a usable one, and asymptotic classification and engineering suitability are different questions. AKS answered a theoretical question definitively and changed no deployment.
04Frequently asked questions
Was AKS a surprise?
Considerable. The problem had resisted for decades and the techniques in use were heavy. The AKS argument is elementary and short enough to present in a lecture, which made the result striking independently of its practical impact.
Have the exponents improved since?
Yes, substantially — variants and sharper estimates for the modulus bound have brought the exponent down considerably. None of the improvements makes it competitive with Miller-Rabin.
Why use elliptic curve primality proving instead when a proof is needed?
Because it produces a certificate that a third party can verify quickly, and it is far faster in practice despite lacking an unconditional complexity bound. Where a proof must be checked rather than trusted, that is the better trade.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 490-500.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.