AKS Primality Test - Algorithm

Algorithm

The algorithm is as follows:

Input: integer n > 1.

1. If n = ab for integers a > 0 and b > 1, output composite.
2. Find the smallest r such that o_r(n) > log2(n).
3. If 1 < gcd(a,n) < n for some a ≤ r, output composite.
4. If n ≤ r, output prime.
5. For a = 1 to do

   if (X+a)n≠ Xn+a (mod Xr − 1,n), output composite;

6. Output prime.

Here o_r(n) is the multiplicative order of n modulo r, log is the binary logarithm, and is Euler's totient function of r.

If n is a prime number, the algorithm will always return prime: since n is prime, steps 1 and 3 will never return composite. Step 5 will also never return composite, because (2) is true for all prime numbers n. Therefore, the algorithm will return prime either in step 4 or in step 6.

Conversely, if n is composite, the algorithm will always return composite: if the algorithm returns prime, then this will occur in either step 4 or step 6. In the first case, since n ≤ r, n has a factor a ≤ r such that 1 < gcd(a,n) < n, which will return composite. The remaining possibility is that the algorithm returns prime in step 6. The authors' article proves that this will not happen because the multiple equalities tested in step 5 are sufficient to guarantee that the output is composite.