← LibraryDeterministic Primality Testing: the AKS AlgorithmEngineering · MathematicsLesson 26/32← PrevNext →
ArticlePublished 6 Aug 2026Updated 5 Aug 20267 min readBy Kevin Jogin
KEVOS® Knowledge Library · Engineering → Mathematics

Engineering/Mathematics/Algorithm engineering

Deterministic Primality Testing: the AKS Algorithm

In 2002 three researchers settled a question open for centuries: primality can be decided in deterministic polynomial time, unconditionally. The algorithm is short enough to state on one page, its proof is elementary, and it is almost never the right tool for the job.

  • Landmark result
  • Computing
  • Theory over practice
  • ≈13 min read
  • Resolved PRIMES ∈ P
PRIMES ∈ PThe resultAnnounced by Agrawal, Kayal and Saxena in 2002; unconditional, deterministic and elementary.
(X+a)n ≡ Xn+aThe identityHolds for all a coprime to n exactly when n is prime.
Õ(ℓ10.5)Original boundLater improved to Õ(ℓ6) by Lenstra and Pomerance.
Not usedIn practiceMiller–Rabin and ECPP are faster by many orders of magnitude at every realistic size.

01

Executive summary

Before 2002, primality was known to be decidable in polynomial time only under unproved hypotheses, or with randomness, or with certificates that were hard to find. The AKS algorithm removed all three qualifications at once.

Its starting point is a polynomial generalisation of Fermat's little theorem that characterises primality exactly — no analogue of Carmichael numbers exists to spoil it. The difficulty is that testing the identity directly costs exponential time, so the algorithm works modulo a small auxiliary polynomial Xr−1, and the technical heart of the proof is showing that a suitable small r exists and that the truncated test is still conclusive.

Why include it in a practitioner's library

Not because it will be deployed, but because it settles what is possible. Security arguments must distinguish between 'no efficient algorithm is known' and 'no efficient algorithm exists'. AKS is a case where the first became the second, and it is a reminder that factoring and discrete logarithms enjoy no proof of hardness either.

Contents

02

The polynomial identity

Theorem T1

Characterisation of primality

(X + a)n ≡ Xn + a in ℤn[X], for gcd(a,n) = 1holds if and only if n is prime

If n is prime, every binomial coefficient C(n,i) for 0 < i < n is divisible by n, so all middle terms vanish — this is the Frobenius endomorphism. If n is composite with a prime power pk ∥ n, then C(n,p) is not divisible by pk, so the coefficient of Xp survives and the identity fails.

Unlike the integer Fermat condition, this test has no false positives at all. The obstacle is purely computational: the left side has n+1 terms, so evaluating it takes time proportional to n, which is exponential in the input length.

The key idea in one sentence

Test the identity modulo Xr−1 for a small r, so that only r coefficients need to be tracked; the proof then shows that if the truncated identity holds for enough values of a, no composite can survive.

Contents

03

The algorithm

AKS primality test (original formulation)

  1. input: integer n > 1
  2. 1. if n is a perfect power b^e (e ≥ 2): return COMPOSITE
  3. 2. find the smallest r with ord_r(n) > (log₂ n)²
  4. 3. for a = 1 .. r: if 1 < gcd(a,n) < n: return COMPOSITE
  5. 4. if n ≤ r: return PRIME
  6. 5. for a = 1 .. ⌊√(φ(r))·log₂ n⌋:
  7. if (X + a)^n ≢ X^n + a (mod X^r − 1, n): return COMPOSITE
  8. 6. return PRIME

Step 5 dominates: each check is a modular exponentiation in the ring ℤ_n[X]/(X^r − 1), costing Õ(r·ℓ²) bit operations, repeated Õ(√r·ℓ) times.

  1. Rule out perfect powers

    Cheap and necessary: the later argument assumes n is not a prime power.

  2. Find a suitable r

    A counting argument shows some r = O(ℓ5) works, so the search terminates quickly. This bound is what drives the original complexity estimate.

  3. Screen for small factors

    The gcd loop catches any composite with a factor below r — a side benefit that also simplifies the analysis.

  4. Test the truncated identity

    The expensive stage. Each value of a requires one exponentiation of a polynomial with r coefficients modulo n.

  5. Conclude

    If every check passes, n is prime — with certainty, and with no hypothesis assumed.

Structure of the correctness proof

Suppose a composite n passed every check, and let p be a prime factor. The polynomials X + a that satisfy the identity generate a multiplicative group in a suitable quotient ring. Counting that group two ways — from below using the many a values, and from above using the number of distinct residues achievable by the exponents nipj — produces a contradiction unless n is a power of p, which step 1 already excluded.

Contents

04

Complexity and improvements

Evolution of the bound
VersionComplexityNote
Original AKS, 2002Õ(ℓ12)As first announced
Revised analysisÕ(ℓ10.5)Sharper bound on r in the published version
Lenstra–Pomerance variantÕ(ℓ6)Uses Gaussian periods in place of Xr−1
Conditional on Artin-type conjecturesÕ(ℓ3)If suitable small r always exist, which is expected but unproved
Practical cost at 1024 bits (order of magnitude, schematic)
Miller–Rabin, 64 rounds≈ 10⁹ bit ops
Pocklington certificate≈ 10⁹ bit ops
ECPP proof≈ 10¹² bit ops
AKS, Õ(ℓ⁶) variant≈ 10¹⁹ bit ops

Polynomial time is not the same as practical

The exponent and the hidden constants matter enormously. At cryptographic sizes AKS is slower than Miller–Rabin by roughly ten orders of magnitude, and slower than ECPP — which produces an actual certificate — by several. Its value is that it exists, is unconditional, and requires no randomness.

Contents

05

AKS in the landscape of primality proving

Comparing certified approaches
MethodOutputNeeds randomness?Needs a hypothesis?Practical at 1024 bits?
Miller–RabinProbable primeYesNoYes — milliseconds
Miller–Rabin, fixed basesProof below a thresholdNoNoYes, for small inputs only
Miller–Rabin, ERH base boundProofNoYes (ERH)Yes, but conditional
PocklingtonCertificateOnly to find the primeNoYes, when p−1 is partly factored
ECPPCertificateYesHeuristic running timeYes — seconds to minutes
AKSYes/no answerNoNoNo

ECPP is the practical choice for certified primes: its certificates are short and verify in milliseconds, even though its own running-time analysis is heuristic.

  • Certificates are often what is actually wanted. A short proof that a third party can check quickly is more useful than an unrepeatable yes/no answer, which is why ECPP and Pocklington dominate in practice.
  • The result changed the theoretical landscape, not the engineering one. No deployed system switched tests; but the question of whether randomness is essential for primality was closed.
  • The analogous question for factoring remains wide open. No polynomial-time classical algorithm is known, and none is proved impossible — which is precisely the assumption underlying RSA.
Contents

06

Quick reference and FAQ

Facts
FactStatement
ResultPRIMES is in P (Agrawal, Kayal and Saxena, 2002)
Core identity(X+a)n ≡ Xn+a in ℤn[X] iff n is prime
TruncationWork modulo Xr−1 with ordr(n) > (log2 n)2
Bound on rO(ℓ5) suffices
Original complexityÕ(ℓ10.5)
Best variantÕ(ℓ6) (Lenstra–Pomerance)
ErrorNone — deterministic and unconditional
Practical useNone at cryptographic sizes
Why does the polynomial identity avoid the Carmichael problem?
Because it is an identity between polynomials, not a single congruence. A composite would have to satisfy it coefficient by coefficient, and the binomial coefficient argument shows that at least one coefficient must fail for every composite. There is no analogue of a number that fools every base.
Does AKS produce a factor when it says composite?
Only incidentally, in the gcd screening step. A failure of the polynomial identity certifies compositeness without exhibiting a factor, exactly like Miller–Rabin.
Would a faster variant ever displace Miller–Rabin?
Only if the exponent dropped to about 3 with small constants. Even then, probabilistic testing at an error level of 2−80 would remain far cheaper, and that error is already below the ambient rate of undetected hardware faults.
Does AKS say anything about factoring?
No. Deciding primality and producing a factorization are different problems, and AKS reinforces the separation: a number can be proved composite in polynomial time while its factors remain out of reach.
Contents

08

References and further reading

  • M. Agrawal, N. Kayal and N. Saxena, 'PRIMES is in P', Annals of Mathematics 160 (2004) 781–793.
  • V. Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005 — Chapter 22.
  • H. W. Lenstra Jr. and C. Pomerance, 'Primality testing with Gaussian periods', J. Eur. Math. Soc. 21 (2019) 1229–1269.
  • A. O. L. Atkin and F. Morain, 'Elliptic curves and primality proving', Math. Comp. 61 (1993) 29–68.

KEVOS® Knowledge LibraryEngineering → MathematicsTaxonomy ID: ENG-MATHPage ID: aks-deterministic-primality-testingReview cycle: annual

Continue learning

Probabilistic Primality TestingArticle · MathematicsNEXT LESSON →Generators and Discrete Logarithms in ℤ*pArticle · MathematicsProbabilistic AlgorithmsArticle · MathematicsComputing Modular Square RootsArticle · Mathematics