Number theory Finite fields and computational number theory Theorem

AKS primality test

Builds on Prime number Multiplicative order Euler's totient function Polynomial ring Quotient ring Fermat's little theorem Freshman's dream Miller–Rabin primality test

Statement

Let $n \ge 2$ be an integer and let $r \ge 2$ be an integer. Assume that $n$ has no prime factor $p \le r$ . Then $\gcd(n, r) = 1$ , so the multiplicative order $\ord_r(n)$ of $n$ modulo $r$ is defined. Assume also that $\ord_r(n) > (\log_2 n)^2$ . Let $\varphi$ be Euler's totient function and let $\ell = \floor{\sqrt{\varphi(r)} \log_2 n}$ . Then the following hold.

The integer $n$ is prime if and only if $n$ is not a perfect power and $(X + a)^n \equiv X^n + a \pmod{X^r - 1,\ n}$ for every integer $a$ with $1 \le a \le \ell$ . Here the congruence is an equality in the quotient ring $\Z[X]/(X^r - 1, n)$ of the polynomial ring $\Z[X]$ . A perfect power is an integer $m^k$ with integers $m, k \ge 2$ .
For every $n \ge 2$ there is an integer $r \le \max\set{3, \ceil{(\log_2 n)^5}}$ with $\ord_r(n) > (\log_2 n)^2$ or $\gcd(n, r) > 1$ .
Hence a deterministic algorithm decides whether $n$ is prime with a number of bit operations polynomial in $\log n$ .

Remarks

The algorithm is due to Manindra Agrawal, Neeraj Kayal and Nitin Saxena, in the paper "PRIMES is in P". It starts from a simple fact: for $\gcd(a, n) = 1$ , the integer $n$ is prime if and only if $(X + a)^n \equiv X^n + a \pmod n$ in $\Z[X]$ . The direct check of this identity costs about $n$ operations, so the test reduces it modulo $X^r - 1$ for a small $r$ . If $n$ is composite with a prime factor $p$ , the congruences for all $a \le \ell$ give a group of polynomials modulo $p$ . This group is forced to be both small and large at once, unless $n$ is a power of $p$ . The algorithm finds the smallest suitable $r$ , checks $\gcd(a, n)$ for $a \le r$ , tests for perfect powers, and then checks the $\ell$ congruences.

For $n$ prime, part 1 holds by Fermat's little theorem and the freshman's dream $(X + a)^p = X^p + a^p$ in characteristic $p$ . The test needs no unproved hypothesis and is never wrong, unlike the Miller–Rabin primality test, which is randomised.

Going deeper

For a student

The test turns the binomial identity $(X + a)^p = X^p + a$ modulo $p$ into a criterion that is cheap to check. The working ring $\Z[X]/(X^r - 1, n)$ has elements of size about $r \log n$ bits, and $r$ is polynomial in $\log n$ by part 2. The proof uses only elementary algebra of finite fields and cyclotomic polynomials, together with a bound on the least common multiple of $1, \ldots, m$ . In practice the test is slower than the Miller–Rabin primality test or elliptic curve methods, so its importance is mainly theoretical. It is a primality test, and it does not find factors; the integer factorization problem is believed to be much harder.

Where this leads

1 page builds on this one.

Integer factorization

Tag	`XMHQCDWZW1`
URI	`m2://XMHQCDWZW1`
Kind	statement, theorem
Writing	W0 stub
MSC	11Y11, 11A51, 68Q25
Status	This copy of the site has no build data. Run `m2 status XMHQCDWZW1`.
About	Primality test, Prime number
Uses	Prime number, Multiplicative order, Euler's totient function, Polynomial ring, Quotient ring, Fermat's little theorem, Freshman's dream, Miller–Rabin primality test
Same as	Wikidata Q294284 Wikipedia AKS primality test
Changed	2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

Used by

Integer factorization