Agrawal-Kayal-Saxena (AKS) Theorem

The AKS primality test determines whether \( n \) is prime using algebraic properties rather than traditional divisibility checks. Instead of directly factoring \( n \), it analyzes the arithmetic structure of \( n \) through polynomial identities.

An algorithm based on the AKS theorem has the key advantage of running in polynomial time with respect to \( \log n \), making it significantly more efficient than classical primality tests.

Note: The term \( \varphi(r) \) refers to the Euler totient function, which counts the number of integers less than \( r \) that are coprime with \( r \).

A Practical Example

Let’s walk through an example of using the AKS primality test to check whether a number is prime.

We take \( n = 5 \) as our test case. Of course, it’s an obvious choice, but using a small number makes the explanation more intuitive.

Step 1: Check whether \( n \) is a prime power

The number \( 5 \) is not a prime power—there is no prime \( p \) and integer \( k > 1 \) such that \( 5 = p^k \). Thus, we move to the next step.

Step 2: Find a suitable value of \( r \)

We need to determine the smallest prime \( r \) such that:

• \( \text{Ord}(r, n) > 4 (\log_2 n)^2 \)
• \( r \leq \lfloor 16 (\log_2 n)^5 \rfloor + 1 \).

For the sake of illustrating the polynomial step of the test, we assume \( r = 3 \). This choice simplifies the computations, although it does not strictly satisfy all the conditions.

Note: In reality, \( r = 3 \) does not strictly meet the theorem’s requirements. Specifically, the multiplicative order of \( n = 5 \) modulo \( r = 3 \) is \( k = \text{Ord}(3,5) = 2 \): \[ 5^2 \equiv 1 \pmod{3} \] However, \( k = 2 \) is too small to satisfy \( 4 (\log_2 5)^2 \), as required.

Step 3: Check for small prime factors

Since \( 5 \) has no prime factors \( \leq 3 \), we proceed.

Note: If \( n \) were composite, say \( n = 6 \), we would detect that it is divisible by 2 or 3 and stop the test immediately.

Step 4: Verify the polynomial congruence

We now check whether the following congruence holds for every \( a = 1, \dots, \lfloor 2 \sqrt{\varphi(r)} \log_2 n \rfloor \):

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

Since \( \varphi(r) \) is the Euler totient function of \( r \), and \( \log_2 n \) is the base-2 logarithm of \( n \), we compute:

For \( r = 3 \), we find \( \varphi(3) = 2 \), so:

\[ 2 \sqrt{\varphi(3)} \log_2 5 = 2 \sqrt{2} \cdot 2.32. \] Approximating \( \sqrt{2} \approx 1.414 \), we get: \[ 2 \times 1.414 \times 2.32 \approx 6.56. \] Thus, for \( r = 3 \) and \( n = 5 \), the upper limit for \( a \) is approximately 6.

Now, let’s test \( a = 1 \):

\[ (x + 1)^5 \equiv x^5 + 1 \pmod{(x^3 - 1, 5)}. \]

Expanding via the binomial theorem:

\[ (x + 1)^5 = x^5 + 5x^4 + 10x^3 + 10x^2 + 5x + 1. \]

Since \( x^3 \equiv 1 \pmod{(x^3 - 1)} \), we substitute \( x^3 = 1 \) and simplify:

\[ x^5 \equiv x^2, \quad x^4 \equiv x. \]

Reducing modulo 5:

\[ x^2 + 5x + 10 + 10x^2 + 5x + 1 \equiv x^2 + 1 \pmod{(x^3 - 1, 5)}. \]

Since terms with coefficients that are multiples of 5 vanish (as they reduce to 0 mod 5), we obtain:

\[ x^2 + 1 \equiv x^2 + 1. \]

Thus, the polynomial congruence holds for \( a = 1 \). However, to confirm that \( n = 5 \) is truly prime, we must check the congruence for all \( a \) values in the range.

Note: The AKS test requires that the congruence holds for all values of \( a \) in the specified range. Verifying only \( a = 1 \) could lead to false positives, as some composite numbers may satisfy the condition for certain values of \( a \) but fail for others.

And so on...