AKS Primality Test

The AKS algorithm is a polynomial-time method for determining whether a given number $ n $ is prime. It is based on the Agrawal-Kayal-Saxena theorem.

How Does the Algorithm Work?
Worked Example

How Does the Algorithm Work?

Check if $ n $ is a perfect power
If $ n = m^k $ for some integers $ m, k $ with $ k > 1 $, then $ n $ is composite since it is the power of a smaller integer. In this case, we immediately conclude that $ n $ is not prime, and the algorithm terminates.
This step efficiently eliminates numbers that are trivially composite, such as perfect powers. For instance, the square of a prime is always composite (e.g., $ 7^2 = 49 $).
Find the smallest suitable $ r $
Determine the smallest integer $ r $ such that the multiplicative order of $ n $ modulo $ r $, denoted as $ \operatorname{Ord}(r, n) $, exceeds $ 4 \log^2 n $: $$ \operatorname{Ord}(r, n) > 4 \log^2 n $$
Compute the greatest common divisor (GCD)
If there exists an integer $ a \leq r $ such that $ 1 < \gcd(a, n) < n $, then $ n $ has a nontrivial divisor, making it composite. In this case, the algorithm terminates.
If $ n \leq r $, then $ n $ is prime
If $ n $ is small enough that $ n \leq r $, then it must be prime, and we conclude the test.
Perform the polynomial congruence test
Verify the following congruence for multiple values of $ a $ in the range $ 1 $ to $ | 2 \sqrt{\phi(r)} \log_2 n | $: $$ (x + a)^n \equiv x^n + a \pmod{x^r - 1, n} $$ If this holds for all tested values of $ a $, then $ n $ is prime; otherwise, $ n $ is composite.

Worked Example

Let's apply the AKS test to determine whether the number

\[ n = 1009 \]

is prime.

Step 1: Checking for a Perfect Power

First, we check whether $ 1009 $ can be expressed as $ m^k $ for some integer $ m $ and $ k > 1 $. Since it is not a perfect power, we proceed to the next step.

Step 2: Finding a Suitable $ r $

We seek the smallest integer $ r $ such that the multiplicative order of $ 1009 $ modulo $ r $ satisfies:

\[ \operatorname{Ord}_r(1009) > 4 \log_2^2(1009) \]

Approximating $ \log_2(1009) \approx 10 $, we find:

\[ 4\log_2^2(1009) \approx 4 \times 10^2 = 400. \]

Thus, we need $ \operatorname{Ord}_r(1009) > 400 $.

For simplicity, let's assume we find a prime $ r $, making Euler’s totient function straightforward to compute: if $ r $ is prime, then $ \phi(r) = r - 1 $.

Choosing $ r = 409 $, we get $ \phi(409) = 408 $.

If $ 1009 $ acts as a generator modulo $ 409 $, then its order is $ \operatorname{Ord}_{409}(1009) = 408 $, which satisfies $ 408 > 400 $.

Note: In an actual implementation, we would verify for each candidate $ r $ that $ \operatorname{Ord}_r(1009) > 4 \log_2^2(1009) $. Here, we assume $ r = 409 $ is a valid choice.

Step 3: Checking GCD Conditions

For each integer $ a $ between 2 and $ r $, we compute:

\[ 1 < \gcd(a,1009) < 1009. \]

Since $ 1009 $ is prime, $ \gcd(a,1009) = 1 $ for all $ a $, meaning no nontrivial divisors are found. We proceed to the next step.

Step 4: Checking If $ n \leq r $

If $ n \leq r $, we could immediately conclude that $ n $ is prime.

Since $ 1009 > 409 $, we move on to the polynomial test.

Step 5: Polynomial Congruence Test

We must verify that for every $ a $ in the range $ 1 $ to $ \lfloor 2\sqrt{\phi(r)}\log_2(1009) \rfloor \approx 404 $, the following congruence holds:

\[ (x+a)^{1009} \equiv x^{1009} + a \pmod{x^{409}-1,\;1009}. \]

Since $ 1009 $ is prime, this congruence holds for all values of $ a $ from 1 to 404.

For example:

\[ (x+1)^{1009} \equiv x^{1009} + 1 \pmod{x^{409}-1,\;1009}, \]

\[ (x+2)^{1009} \equiv x^{1009} + 2 \pmod{x^{409}-1,\;1009}, \]

\[ (x+3)^{1009} \equiv x^{1009} + 3 \pmod{x^{409}-1,\;1009}, \]

\[ \vdots \]

Conclusion

Since $ 1009 $ has passed all the steps of the AKS test, including the polynomial congruence verification, we conclude that $ 1009 $ is a prime number.

And that's it!