Contents

AKS Primality Test

The AKS primality test is a deterministic primality test. It was the foremost test that proved that the language PRIMES is in P class finally settling the issue about where PRIMES belongs.

Intuition

AKS test is an extension of Fermat’s Little Theorem to polynomials.

Lemma 3

Let \(a,n \in \mathbb{Z}\) with \((a, n) = 1\). Then \(n\) is prime iff

\[(X + a)^n \equiv X^n + a \quad (\text{mod} n)\]

Here, \(X\) is a symbol that is part of the polynomial.

Proof. Using Binomial theorem,

\[(X + a)^n = \sum_{k = 0}^{n} \binom{n}{k} X^{n - k} a^k\]

For \(0 < k < n\),

\[\binom{n}{k} = \frac{n!}{(n - k)! k!} = \frac{n \cdot (n - 1) \cdot (n - 2) \cdots (n - k + 1)}{k!}\]

Suppose \(n\) is prime. Then on modulus \(n\), \(n | n\) in the numerator but nothing in the denominator since \(k < n\) and \((k,n) = 1\) due to \(n\) being prime.

Now, we are left with the \(0^{th}\) and \(n^{th}\) terms both having coefficients \(= 1\).

For, the \(0^{th}\) term, \(X^n \text{ mod } n\) remains. As for the \(n^{th}\) term, \(a^{n} = a \text{ mod } n\) by Fermat’s Little Theorem.

To prove the other side of the biconditional, we will prove the contrapositive.

Suppose, \(n\) is composite. Therefore, we assume a prime factor \(p\) of \(n\). Therefore, by fundamental theorem of arithmetic, we know for some \(e > 0,\quad p^e | n\) but \(p^{e + 1} \nmid n\).

For the \(p^{th}\) term, coefficient \(= \binom{n}{p} = \frac{n \cdot (n - 1) \cdot (n - 2) \cdots (n - p + 1)}{p!}\).

\(p^e\) divides only \(n\) in the numerator and nothing else (since the numerator is consecutive numbers of count \(p\) and only \(n\) is divisible by them). But there is an additional \(p\) in the denominator due to \(p!\).

Which implies that, \(p^{e - 1} | \binom{n}{p}\) but \(p^{e} \nmid \binom{n}{p}\). Which means that \(n \nmid \binom{n}{p}\) and therefore this term does not vanish.

Thus, we do not reach the \(X^n + a\) form.

This lemma in itself gives a condition to do primality testing. But computing the coefficients of \((X + a)^n\) is exponential in the size of \(n\) which makes the test extremely slow for large inputs.

This is solved in the AKS test by evaluating the polynomials on both sides modulo another polynomial, \(X^r - 1\) and checking for several different \(a\)’s.

So we test the congruence

\[(X + a)^n \equiv X^n + a \quad (\text{mod } X^r - 1, n)\]

This will lower the degree of the polynomial and thus reduce the number of coefficients needed to be calculated to confirm the test.

Algorithm 5 (AKS Primality Test)

Input: \(n \ge 2\)

  1. If n = \(a^b\) for \(a \in \mathbb{N}\) and \(b > 1\), return COMPOSITE

  2. Find the smallest \(r\) such that \(ord_r(n) \not \le log^2 n\)

  3. If \(1 < (a, n) < n\) for some \(a \le r\), return COMPOSITE

  4. If \(n \le r\), return PRIME

  5. For a = 1 to \(\lfloor \sqrt{\phi(r)} log n \rfloor\):

  6. If \((X + a)^n \not \equiv X^n + a \; (\text{mod } X^r − 1, n)\), return COMPOSITE.

  7. Return PRIME.

Here, \(ord_r(n)\) is the order of the element \(n\) within the group \(\mathbb{Z}^*_r\).