Engineering / Mathematics — Primality Testing
Deterministic Primality Testing: The Basic Idea
The polynomial identity underlying AKS primality testing and the obstacle that makes it non-trivial to exploit.
Executive summary
AKS rests on a polynomial generalisation of Fermat's little theorem that characterises primality exactly, with no exceptions of Carmichael type.
The identity is easy to state and expensive to check directly; the algorithm's content is a method for checking it cheaply enough.
Learning objectives
- State the polynomial criterion for primality.
- Explain why it has no false positives.
- Identify the cost obstacle and the strategy for overcoming it.
01The criterion
Polynomial characterisation of primality
For n ≥ 2 and any a coprime to n,
(X + a)^n ≡ X^n + a (mod n) in Z_n[X]
if and only if n is prime.
One direction is the freshman's dream made rigorous: when n is prime, every binomial coefficient C(n, i) for 0 < i < n is divisible by n, because n appears in the numerator and cannot be cancelled by the smaller factors in the denominator.
The converse is what makes the criterion valuable. If n is composite with prime factor p and p^k exactly divides n, then the coefficient C(n, p) is not divisible by n, so the identity fails.
02The cost obstacle
The natural remedy is to work modulo a small polynomial as well as modulo n, reducing the degree.
(X + a)^n ≡ X^n + a (mod n, X^r − 1)Now the polynomials have degree below r, so each multiplication is cheap. The difficulty is that this weaker congruence can hold for some composites, so it no longer characterises primality on its own.
03Restoring the characterisation
The AKS insight is that checking the reduced congruence for enough values of a, with r chosen appropriately, restores the exact characterisation.
Choose r
Find a small r such that the multiplicative order of n modulo r exceeds (log n)².
Bound r
Such an r exists below a polynomial bound in log n, which is what keeps the polynomial arithmetic cheap.
Test a range of a
Check the reduced congruence for every a up to a bound derived from r and n.
Conclude
If all checks pass and n is not a perfect power, n is prime.
The proof that this suffices is the technical heart of the result. It argues that a composite passing all the checks would generate too large a set of distinct residues in a certain quotient ring, contradicting a counting bound.
The outcome was the first unconditional deterministic polynomial-time primality test, settling a question that had been open for decades.
04Frequently asked questions
Why does working modulo X^r − 1 break the characterisation?
Because reduction collapses distinct polynomials together, so a composite whose expansion differs from X^n + a only in coefficients that get merged will pass. Testing many values of a is what rules this out.
Is the perfect power check really necessary?
Yes. Perfect powers can satisfy the congruences for structural reasons, so they are removed by a separate cheap test before the main loop begins.
Does AKS replace Miller-Rabin?
No. It is orders of magnitude slower and is not used for practical primality testing. Its significance is theoretical — it established that primality is in P.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 489-490.
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.