AKS Primality Test: How the Algorithm Works

The AKS primality test is a deterministic algorithm that decides whether an integer greater than 1 is prime or composite. Manindra Agrawal, Neeraj Kayal, and Nitin Saxena announced the method in 2002; the journal version appeared in 2004 under the title PRIMES is in P.AKS matters because it proved that general primality testing can be done in deterministic polynomial time without random choices and without assuming an unproved hypothesis. Its main idea is unusual: instead of looking for divisors directly, it tests a polynomial congruence inside a carefully limited polynomial ring.

Why Primality Testing Is a Complexity Problem

A direct primality test can try dividing n by integers up to √n. That method is mathematically valid, but complexity is measured against the size of the input, not the numeric value of the input.An integer n needs about log2(n) bits to store. If that bit length is called L, then n is roughly 2L. A search extending to √n therefore grows roughly like 2L/2, which is exponential in the input length.

The Polynomial Identity Behind AKS

For an integer a with gcd(a,n)=1, consider the identity When n=p is prime, the binomial theorem explains why it works. Expanding the left side gives Every middle binomial coefficient C(p,k), for 0<k<p, is divisible by p. Those terms vanish modulo p. Fermat’s little theorem gives ap ≡ a (mod p), leaving The full identity is strong enough to characterize primality under the stated coprimality condition. There is a computational problem, however: testing it directly can require handling about n coefficients. That is too much when the target is running time polynomial in log n.

Why AKS Also Uses Modulo X^r − 1

AKS reduces the polynomial identity a second time: The notation describes two reductions. Polynomial coefficients are reduced modulo n, while powers of X are reduced using Xr ≡ 1.For example, if r=5: High powers therefore wrap back into degrees below r. Instead of carrying a polynomial whose degree can climb toward n, the computation can keep only r coefficient positions. Choosing a suitable r makes the reduced identity strong enough for the later primality argument.

How the AKS Algorithm Works

Step 1: Reject Perfect Powers

AKS begins by checking whether Numbers such as 64=26, 81=34, and 125=53 are composite and stop here.This check also matters to the later proof. The algebraic argument eventually restricts a difficult surviving composite case to a prime power. Removing nontrivial perfect powers first lets the later polynomial stage finish the classification.

Step 2: Find a Suitable r

AKS next finds the smallest r such that Here, ordr(n) is the multiplicative order of n modulo r. It is defined when gcd(n,r)=1.

What multiplicative order means

The multiplicative order is the smallest positive integer k for which Take n=2 and r=5. The residues cycle like this: AKS does not accept an arbitrary small value of r. Requiring a large enough order prevents the powers of n modulo r from repeating too soon. The later proof then has enough distinct algebraic behavior to work with.

Step 3: Search for an Immediate GCD Witness

For integers up to r, AKS checks whether any value satisfies If it does, the test already has a nontrivial divisor of n. For example, with n=35 and a=5, gcd(5,35)=5. No polynomial calculation is needed; 35 is composite.

Step 4: Why n ≤ r Can Return Prime

If no nontrivial GCD was found for values through r and n≤r, AKS can return prime. A composite n would have a nontrivial factor smaller than n, and that factor would already lie inside the checked range.

Step 5: Test the Polynomial Congruences

The main algebraic work now begins. AKS tests for where φ(r) is Euler’s totient function. If even one required value of a breaks the congruence, AKS returns composite.Testing one value of a would not be enough after reducing modulo Xr−1. Some composite numbers can satisfy a reduced identity for selected values. The bounded family of a values restores enough separating strength while keeping the number of tests polynomial in the input length.

Step 6: Return Prime

If the number is not a perfect power, has no nontrivial GCD witness in the required range, and passes every required polynomial congruence, AKS returns PRIME.This is an exact verdict. Standard AKS does not end with “probably prime,” and its correctness does not depend on random bases.

AKS Pseudocode

AKS(n)

1. if n = a^b for integers a > 1 and b > 1:
       return COMPOSITE

2. find the smallest r such that
       ord_r(n) > (log2 n)^2

3. if 1 < gcd(a,n) < n for some a ≤ r:
       return COMPOSITE

4. if n ≤ r:
       return PRIME

5. for a = 1 to floor(sqrt(phi(r)) * log2 n):
       if (X+a)^n != X^n+a mod (X^r-1,n):
           return COMPOSITE

6. return PRIME

Why the Polynomial Test Can Prove Primality

The correctness argument has two directions.If n is prime, the perfect-power and GCD steps cannot reject it. The prime polynomial identity also ensures that the required congruences hold, so a prime reaches a PRIME result.The harder direction starts with a composite number that survives the early checks. The chosen value of r and the repeated polynomial identities create enough distinct elements in a finite algebraic setting to place a strong bound on what such a composite can look like. The proof forces the surviving case toward a prime power. Step 1 has already removed nontrivial perfect powers, so a composite cannot reach the final PRIME verdict.

What “PRIMES Is in P” Means

P is the class of decision problems that a deterministic algorithm can solve in polynomial time relative to input length. For primality testing, the decision problem is simple to state: AKS showed that this question has an unconditional deterministic polynomial-time solution for general integers.

AKS Time Complexity

The journal version of AKS gives a proved running-time bound of Õ(log15/2 n) for the stated algorithm. The soft-O notation Õ suppresses additional polylogarithmic factors.The same paper also notes a modified version due to Hendrik Lenstra and Carl Pomerance with a proved bound of Õ(log6 n). This distinction matters. Describing the original AKS algorithm simply as O(log6 n) mixes the original analysis with a later modification and also drops the meaning of soft-O notation.

How common primality tests differ

Method	Verdict	Randomness	Typical role
Trial division	Exact	None	Small integers and basic demonstrations
Miller–Rabin	Probable-prime result in its general randomized form; a compositeness witness is exact	Usually used with selected or random bases	Fast practical screening
AKS	Exact	None	Deterministic polynomial-time primality and complexity theory

Why AKS Is Rarely the Fastest Practical Choice

A polynomial-time bound is an asymptotic statement. It does not guarantee the smallest running time for number sizes used in ordinary software.AKS performs polynomial arithmetic in the quotient ring Zn[X]/(Xr−1). Repeated modular polynomial multiplication and exponentiation create much more overhead than faster practical primality tests usually need.AKS is therefore best known for settling the complexity question around deterministic primality testing. A program can also give deterministic results over a fixed integer range without using AKS. For a direct verdict on a particular integer, the Prime Number Checker provides the practical test, while AKS explains how general primality testing can be placed in deterministic polynomial time.

What the Computer Stores in Step 5

A straightforward implementation should not fully expand (X+a)n and reduce it only afterward. It can represent a polynomial by an array of r coefficients: After polynomial multiplication, every coefficient is reduced modulo n. Any term whose exponent reaches r or more wraps around because Xr≡1. Exponentiation can use repeated squaring, similar to modular integer exponentiation, but with coefficient arrays instead of single integers.For r=5, a product term such as 7X8 is stored in the X3 position because X8≡X3. Its coefficient is then reduced modulo n.

The 2019 Erratum to the AKS Paper

A later correction matters when describing the published proof accurately. In 2019, Agrawal, Kayal, and Saxena issued an erratum for the proof of Lemma 4.3 in the 2004 paper.The original proof used a construction of r that did not fully handle a case where the resulting value might fail to be coprime to n. In that case, ordr(n) would be undefined. The erratum changes the construction used in the proof so that the needed r is coprime to n and the multiplicative-order argument goes through.The correction repairs the affected proof. It does not turn AKS into a probabilistic test or replace its polynomial-congruence method with another primality algorithm.

Common Misreadings of AKS

“AKS checks every possible divisor.”

No. Its defining stage checks polynomial congruences. The GCD scan covers only a bounded range tied to r.

“Polynomial time means polynomial in n.”

No. The relevant input length is about log2 n bits. AKS is polynomial in that input length.

“AKS returns probably prime.”

No. AKS is deterministic and gives an exact prime/composite decision when implemented correctly.

“AKS factors composite numbers.”

No. An early GCD check may expose a factor, but factorization is not the task the algorithm promises to solve.

“The 2019 erratum means AKS no longer proves PRIMES is in P.”

No. The erratum supplies a corrected argument for the affected lemma. The deterministic polynomial-time primality result remains.

The Mathematical Idea in One Chain

That sequence separates AKS from a divisibility search or a probable-prime test. The algorithm turns a polynomial identity into a finite deterministic procedure whose running time is polynomial in the number of bits needed to write n.