The AKS Primality Test

Unlike the two tests described in our article on the Fermat and Miller-Rabin tests, the Agrawal-Kayal-Saxena (AKS) primality test does not look for non-trivial square roots or Fermat witnesses. It is a deterministic algorithm, which means that — unlike the Miller-Rabin and Fermat tests — it can prove primality or compositeness with certainty.

The starting point for the AKS test is the following theorem.

Theorem 1. Suppose we have integers $n \ge 2$ and $a \ge 0$. If $n$ is prime, then $(x - a)^n \equiv x^n - a \pmod{n}$. If, on the other hand, $n$ is composite and $a$ and $n$ are coprime (their greatest common divisor is $1$), then $(x - a)^n \not\equiv x^n - a \pmod{n}$.

Since the theorem holds, it implies a straightforward primality test: take an input $n$, choose some $a$, and check whether the two polynomials leave the same remainder when divided by $n$.

Implementing this directly, however, runs into trouble. For large values of $n$, the number of coefficients to evaluate in the polynomial $(x - a)^n$ becomes correspondingly large.

So, instead of comparing the two polynomials modulo $n$ alone, the AKS algorithm also divides both by $x^r - 1$, where $r$ is chosen to be small and suitable (see below). The remainders can then be compared modulo $n$.

The indirect test is therefore to evaluate the following, which we will call Eq. 1:

$$(x + a)^n \equiv x^n + a \pmod{x^r - 1,\ n}.$$

Bringing this together — and adding a few details omitted from this brief exposition (see the AKS primality test article for more) — many implementations of the AKS algorithm follow these steps:

• Is $n$ a perfect power? If so, return composite. In other words, if there exist integers $a, b > 1$ such that $n = a^b$, then $n$ is composite.
• Find the small, suitable value of $r$ mentioned above. Starting from $r = 2$, find the smallest $r$ such that the multiplicative order of $n$ modulo $r$ exceeds $(\log_2 n)^2$.
• If $1 < \gcd(a, n) < n$ for some $a \le r$, then $n$ is composite.
• If $n \le r$, then $n$ is composite.
• For each $a \in \{1, 2, \dots, \lfloor \sqrt{\varphi(r)}\, \log_2 n \rfloor\}$, where $\varphi(r)$ is Euler’s totient function, check whether the congruence in Eq. 1 holds. If it fails for any such $a$, then $n$ is composite.
• If the algorithm reaches this point without halting, then $n$ is definitely prime.