AKS Primality Test

•  Mar 2020

•  7-minute read

•  Academic Commentaries

The Agrawal, Kayal, and Saxena (AKS) primality test doesn't look for fake square roots or Fermat witnesses, like the two tests described in my last post. It is a deterministic algorithm, meaning that - unlike the Miller-Rabin and Fermat tests - it can provably determine primality or compositeness.

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

Theorem 1: Suppose we have integers \(n \geq 2\) and \(a \geq 0\). If \(n\) is prime, then \((x - a)^n \equiv x^n - a \pmod{n}\). Else, if \(n\) is composite and \(a\) and \(n\) are coprime (that is, their greatest common divisor is \(1\)), then \((x - a)^n \not\equiv x^n - a \pmod{n}\).

If the theorem holds, which it does, then it implies a straightforward primality test. Take an input \(n\), choose some \(a\), and see whether the two polynomials have the same remainder after being divided by \(n\).

Implementing this test directly, however, would mean that, when dealing with massive values of \(n\), the number of coefficients that would have to be evaluated in the polynomial \((x - a)^n\) would be correspondingly massive.

So, instead of comparing the two polynomials \(\pmod{n}\), the AKS algorithm divides both by \(x^r - 1\), where \(r\) is, ideally, small and, moreover, chosen suitably (see below). After this, the remainders can be compared \(\pmod{n}\).

So, the indirect approach is to evaluate the following, which we will call Eq. 1: $$(x + a)^n \equiv x^n + a \pmod{x^r - 1, n}.$$

Bringing all this together, but also adding a few things that aren't mentioned in this brief exposition (see here for more), the steps followed in many implementations of the AKS algorithm, including my own, are the following:

• Is \(n\) a perfect power? If so, return composite. In other words, if there exist integers \(a\), \(b \gt 1\) such that \(n = a^b\), then \(n\) is composite.
• Now, find the suitable, small value of \(r\) mentioned above. Starting with \(r = 2\), find the smallest \(r\) such that the multiplicative order of \(n\) modulo \(r\) is greater than \((\log_2 n)^2\).
• If \(1 \lt \gcd(a, n) \lt n\) for some \(a \leq r\), then \(n\) is composite.
• If \(n \leq r\), then \(n\) is composite.
• For \(a \in \{1, 2, ..., \lfloor \sqrt{\varphi(r)} \log_2(n) \rfloor\}\), where \(\varphi(r)\) is Euler's totient function, see if the congruence in Eq. 1 is satisfied. If not, then \(n\) is composite.
• If the algorithm has reached this point without halting, then the math shows that \(n\) is definitely prime.