Proofs: AKS primality test

The AKS test returns true exactly when n is prime full

This proof shows: correctness, termination.

We use the pseudocode AKS$(n)$ of the page, after Agrawal, Kayal and Saxena (Annals of Mathematics 160, 2004, Section 4). Write $\lg$ for the base 2 logarithm, $o_r(m)$ for the order of $m$ modulo $r$ when $\gcd(m, r) = 1$, and $\varphi$ for Euler's totient. "$f \equiv g \pmod{X^r - 1, m}$" means that $f - g$ lies in the ideal generated by $X^r - 1$ and $m$ in $\mathbb{Z}[X]$.

Lemma 1 (termination of line L3). For $n \ge 2$ there is an $r \ge 2$ with $\gcd(r, n) = 1$ and $o_r(n) > (\lg n)^2$, so line L3 ends.

Proof. Let $k = \lfloor (\lg n)^2 \rfloor$ and $N = n \prod_{i=1}^{k} (n^i - 1)$, a positive integer since $n \ge 2$. Take a prime $r$ that does not divide $N$. Then $r \nmid n$, so $\gcd(r, n) = 1$, and $n^i \not\equiv 1 \pmod r$ for $1 \le i \le k$, so $o_r(n) > k$, that is, $o_r(n) > (\lg n)^2$ as $o_r(n)$ is an integer. The search of line L3 tries $r = 2, 3, \ldots$ in order, so it stops at the least such $r$. (Lemma 4.3 of the paper shows that $r \le \max(3, \lceil (\lg n)^5 \rceil)$.) $\square$

Lemma 2 (polynomial Fermat for primes). If $n$ is prime, then $(X + a)^n \equiv X^n + a \pmod n$ for every integer $a$.

Proof. By the binomial theorem $(X + a)^n = \sum_{i=0}^{n} \binom{n}{i} a^{n-i} X^i$. For $0 < i < n$, $\binom{n}{i} = \frac{n!}{i!(n-i)!}$ and the prime $n$ divides the numerator but not the denominator, so $n \mid \binom{n}{i}$. The two outer terms are $X^n$ and $a^n \equiv a$, by Fermat's little theorem. $\square$

Lemma 3 (primes return true). If $n$ is prime, AKS$(n)$ returns true.

Proof. Line L1 does not fire as $n \ge 2$, and line L2 does not fire, as a prime is not $a^b$ with $a, b \ge 2$. In line L4, $\gcd(a, n) \in \{1, n\}$ for every $a$, so it does not fire. If $n \le r$, line L5 returns true. Otherwise, for each $a$, Lemma 2 gives $(X + a)^n \equiv X^n + a \pmod n$, hence also modulo $(X^r - 1, n)$, so line L8 does not fire and line L9 returns true. $\square$

From now on, suppose that AKS$(n)$ returns true. If it does so at line L5, then $n \le r$ and line L4 found no $a \le r$ with $1 < \gcd(a, n) < n$; in particular no $a$ with $2 \le a \le n - 1$ divides $n$, so $n$ is prime. So assume it returns true at line L9. Then $n \ge 2$, $n$ is not a perfect power, $n > r$, $\gcd(r, n) = 1$, $o_r(n) > (\lg n)^2$, $\gcd(a, n) = 1$ for $1 \le a \le r$, and, with $\ell = \lfloor \sqrt{\varphi(r)} \lg n \rfloor$,

where $a = 0$ holds trivially. We show that $n$ is prime.

Setup. Since $o_r(n) > (\lg n)^2 \ge 1$, $n \not\equiv 1 \pmod r$. If every prime factor $q$ of $n$ had $q \equiv 1 \pmod r$, then $n \equiv 1$; so some prime $p \mid n$ has $p \not\equiv 1 \pmod r$, that is, $o_r(p) > 1$ (note $\gcd(p, r) = 1$ as $\gcd(n, r) = 1$). Since $\gcd(a, n) = 1$ for all $a \le r$, $p > r$. Also $o_r(n) \le \varphi(r)$, so $\sqrt{\varphi(r)} > \lg n$ and $\ell < \varphi(r) < r < p$. Reducing the congruences above modulo $p$:

By Lemma 2 for the prime $p$:

Work in $\mathbb{F}_p[X]$. Call an integer $m \ge 1$ introspective for $f \in \mathbb{F}_p[X]$ if $f(X)^m \equiv f(X^m) \pmod{X^r - 1}$.

Lemma 4. If $m$ and $m'$ are introspective for $f$, so is $m m'$. If $m$ is introspective for $f$ and for $g$, it is introspective for $f g$.

Proof. Substituting $X^m$ for $X$ in $f(X)^{m'} \equiv f(X^{m'}) \pmod{X^r - 1}$ gives $f(X^m)^{m'} \equiv f(X^{m m'}) \pmod{X^{mr} - 1}$, and $X^r - 1$ divides $X^{mr} - 1$, so this also holds modulo $X^r - 1$. Hence $f(X)^{m m'} = (f(X)^m)^{m'} \equiv f(X^m)^{m'} \equiv f(X^{m m'})$. The second claim is $(fg)(X)^m = f(X)^m g(X)^m \equiv f(X^m) g(X^m) = (fg)(X^m)$. $\square$

Lemma 5. The numbers $p$ and $n / p$ are introspective for each $X + a$, $0 \le a \le \ell$.

Proof. For $p$ this is (2). For $m = n/p$, let $u = (X + a)^m - (X^m + a)$. In $\mathbb{F}_p[X]$ the map $g \mapsto g^p$ is a ring homomorphism with $c^p = c$ on $\mathbb{F}_p$, so $u^p = (X + a)^n - (X^n + a)$, which is $0$ modulo $X^r - 1$ by (1). Since $p \nmid r$, $X^r - 1$ and its derivative $r X^{r-1}$ are coprime, so $X^r - 1$ is squarefree in $\mathbb{F}_p[X]$. Each irreducible factor $h$ of $X^r - 1$ divides $u^p$, hence $u$; as these factors are distinct, their product $X^r - 1$ divides $u$. $\square$

Let $I = \{ (n/p)^i p^j : i, j \ge 0 \}$ and $P = \{ \prod_{a=0}^{\ell} (X + a)^{e_a} : e_a \ge 0 \}$. By Lemmas 4 and 5, every $m \in I$ is introspective for every $f \in P$.

Let $G$ be the set of residues modulo $r$ of the elements of $I$. All of them are units modulo $r$, and $G$ is closed under products, so $G$ is a subgroup of $(\mathbb{Z}/r\mathbb{Z})^\times$. Let $t = |G|$. Then $t \le \varphi(r)$, and $G$ contains the powers of $n = (n/p) \cdot p$, so $t \ge o_r(n) > (\lg n)^2$.

Let $Q_r$ be the $r$-th cyclotomic polynomial. It divides $X^r - 1$, and over $\mathbb{F}_p$ it is a product of irreducible factors of degree $o_r(p) > 1$. Fix one such factor $h$ and let $F = \mathbb{F}_p[X] / (h)$, a finite field in which the class $\xi$ of $X$ is a primitive $r$-th root of unity. Let $\mathcal{G}$ be the set of images of $P$ in $F$. No $X + a$ maps to 0, since $\deg h > 1$, so $\mathcal{G}$ is a subset of $F^\times$ closed under products, that is, a subgroup.

Lemma 6 (lower bound). $|\mathcal{G}| \ge \binom{t + \ell}{t - 1}$.

Proof. Let $f, g \in P$ have degree below $t$ and the same image in $F$. For $m \in I$, $f(X)^m \equiv f(X^m)$ and $g(X)^m \equiv g(X^m)$ modulo $X^r - 1$, hence modulo $h$, so $f(\xi^m) = f(\xi)^m = g(\xi)^m = g(\xi^m)$ in $F$. As $\xi^r = 1$, $\xi^m$ depends only on $m \bmod r$, and as $\xi$ has order $r$, the $t$ residues in $G$ give $t$ distinct elements $\xi^m$. So $f(Y) - g(Y)$, of degree below $t$, has $t$ roots in the field $F$, and $f = g$. Now the numbers $0, 1, \ldots, \ell$ are distinct modulo $p$, as $\ell < p$, so the polynomials $\prod_a (X + a)^{e_a}$ with $\sum_a e_a \le t - 1$ are distinct elements of $P$ of degree below $t$, by unique factorization in $\mathbb{F}_p[X]$. There are $\binom{(t - 1) + (\ell + 1)}{t - 1} = \binom{t + \ell}{t - 1}$ of them, and their images are distinct. $\square$

Lemma 7 (upper bound). If $n$ is not a power of $p$, then $|\mathcal{G}| \le n^{\sqrt t}$.

Proof. Let $s = \lfloor \sqrt t \rfloor$ and $\hat I = \{ (n/p)^i p^j : 0 \le i, j \le s \}$. If $(n/p)^i p^j = (n/p)^{i'} p^{j'}$ with $(i, j) \ne (i', j')$, then $i \ne i'$, and $(n/p)^{|i - i'|}$ is a power of $p$, so $n/p$ and $n$ are powers of $p$. So, as $n$ is not, $\hat I$ has $(s + 1)^2 > t$ elements, and two of them, $m_1 > m_2$, have the same residue modulo $r$. Then for every $f \in P$, $f(X)^{m_1} \equiv f(X^{m_1}) \equiv f(X^{m_2}) \equiv f(X)^{m_2} \pmod{X^r - 1}$, since $X^{m_1} \equiv X^{m_2} \pmod{X^r - 1}$. So every element of $\mathcal{G}$ is a root in $F$ of $Y^{m_1} - Y^{m_2}$, a nonzero polynomial of degree $m_1$, and $|\mathcal{G}| \le m_1 \le (n/p)^s p^s = n^s \le n^{\sqrt t}$. $\square$

Lemma 8. $|\mathcal{G}| > n^{\sqrt t}$.

Proof. Let $B = \lfloor \sqrt t \lg n \rfloor$. Since $t > (\lg n)^2$, $\sqrt t > \lg n$, so $t > \sqrt t \lg n \ge B$ and $t - 1 \ge B$. Since $t \le \varphi(r)$, $\ell = \lfloor \sqrt{\varphi(r)} \lg n \rfloor \ge B$. Also $n > r \ge 2$ and $(\lg n)^2 < t \le \varphi(r) < r < n$; for $n \ge 3$, $\sqrt t \lg n > (\lg n)^2 > 2$, so $B \ge 2$. The binomial coefficient $\binom{t + \ell}{t - 1} = \binom{(\ell + 1) + (t - 1)}{t - 1}$ grows with $t - 1$ and with $\ell$, so by Lemma 6

For $B \ge 2$, $\binom{2B + 1}{B} > 2^{B + 1}$: it holds for $B = 2$ ($10 > 8$), and going from $B$ to $B + 1$ multiplies the left side by $\frac{(2B + 3)(2B + 2)}{(B + 2)(B + 1)} = \frac{2(2B + 3)}{B + 2} > 2$. Finally $B + 1 > \sqrt t \lg n$, so $2^{B + 1} > 2^{\sqrt t \lg n} = n^{\sqrt t}$. $\square$

Theorem. For every integer $n \ge 0$, AKS$(n)$ ends, and it returns true if and only if $n$ is prime.

Proof. Termination. Line L1 handles $n < 2$. Line L2 tries finitely many exponents, line L3 ends by Lemma 1, and the loops of lines L4 and L7 are bounded by $r$ and $\ell$. Each check in line L8 is a power computed with $\lfloor \lg n \rfloor$ squarings.

Primes. By Lemma 3 a prime returns true.

Composites. Suppose a composite $n$ returns true. A return at line L5 forces $n$ prime, as shown above, so the return is at line L9, and the setup applies with a prime $p \mid n$. Lemmas 7 and 8 together force $n$ to be a power of $p$, say $n = p^k$, and $k \ge 2$ as $n$ is composite. Then $n = p^k$ is a perfect power and line L2 would have returned false, a contradiction. So a composite $n$ returns false, and so do $0$ and $1$, at line L1. $\blacksquare$