AKS Primality Testing

AKS Primality Testing Algorithm

Short Description

The AKS (Agrawal–Kayal–Saxena) algorithm is a deterministic polynomial-time algorithm used to test whether a given number is prime. Unlike probabilistic methods such as the Fermat or Miller–Rabin tests, AKS always produces a correct result without relying on randomness. Introduced in 2002 by Agrawal, Kayal, and Saxena, this algorithm resolved a long-standing open problem in computer science by proving that primality testing belongs to the complexity class P.

2. Mathematical Foundation

2.1 Fermat’s Little Theorem (Classical)

If $p$ is prime and $a$ is not divisible by $p$:

$$a^{p} \equiv a \pmod{p}$$

This is the basis of many probabilistic tests.

❗ Problem: Some composite numbers (Carmichael numbers) also satisfy this.

---

3. Key Insight Behind AKS

Instead of working with numbers, AKS works with polynomials.

AKS Theorem

For an integer $n > 1$,

$$n \text{ is prime } \iff (x + a)^n \equiv x^n + a \pmod{(n,\; x^r - 1)}$$

for suitably chosen values of $a$ and $r$.

This polynomial identity always holds for primes, and fails for composites.

---

4. Why Does This Work?

4.1 If $n$ is prime

Using the binomial theorem:

$$(x + a)^n = x^n + \binom{n}{1}x^{n-1}a + \cdots + a^n$$

When $n$ is prime:

• All binomial coefficients $\binom{n}{k}$ for $1 \le k \le n-1$ are divisible by $n$
  

• So modulo $n$:

$$(x + a)^n \equiv x^n + a^n \equiv x^n + a \pmod{n}$$

✅ Identity holds.

---

4.2 If $n$ is composite

At least one binomial coefficient is not divisible by $n$.

So the identity breaks, revealing compositeness.

---

5. The AKS Algorithm – Step by Step

Step 1: Check if $n$ is a perfect power

The algorithm begins by checking whether the given number $n$ can be expressed as:

$$n=a^b\text{where }a>1\text{ and }b>1$$

If such a representation exists, then $n$ is composite.
This step quickly eliminates numbers like 16, 27, or 64.

📌 Example:

• $64=2^{\mathrm{6\to \; composite}}$

• $27 = 3^3$ → composite

---

Step 2: Find a suitable $r$

The next step is to find the smallest integer $r$ such that the multiplicative order of $n$ modulo $r$ is greater than $(\log n{)}^2$

$$\text{ord}_r(n) > (\log n)^2$$

Where:

• ${\text{ord}}_r(n)=\; smallest$$k$ such that $n^k \equiv 1 \pmod{r}$
  

This step limits polynomial degree and ensures efficiency.

This step limits polynomial degree and ensures efficiency.

This condition ensures that polynomial computations later in the algorithm remain efficient and bounded. The choice of r is crucial for guaranteeing polynomial-time complexity.

---

Step 3: Check for small divisors

For every integer $a$ from 2 to $r$, the algorithm checks:

$$\gcd (a,n)$$

If the GCD is greater than 1 but less than $n$, then $n$ has a non-trivial divisor and is therefore composite.

For all $2\le d\le \mathrm{r:}$

• If $\gcd(n, d) > 1$, then composite

📌 Example:

• $n = 21$, $\gcd (21,3)=\mathrm{3\; \to \; composite}$

---

Step 4: If $n \le r$, declare PRIME

Small numbers can be directly handled.

If the number $n$ is less than or equal to $r$, and it has passed all previous checks, it is declared prime.
This step avoids unnecessary polynomial computations for small values of $n$.

---

Step 5: Polynomial Congruence Test (Core Step)

This is the heart of the AKS algorithm. For values of $a$ from 1 up to:

$$\lfloor \sqrt{\varphi (r)}\cdot \log n\rfloor$$

This step is a generalization of Fermat’s Little Theorem to polynomial rings and guarantees deterministic correctness.

For:

$$a = 1 \text{ to } \lfloor \sqrt{\phi(r)} \log n \rfloor$$

Check:

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

$$<br>$$

• If this congruence fails for any value of $a$, the number is composite.

• If it holds for all tested values, the number is prime.

---

6. Worked Examples

---

Example 1: $n = 7$(Prime)

Check:

$$(x + 1)^7 = x^7 + 7x^6 + \cdots + 1$$

Modulo $7$:

$$(x + 1)^7 \equiv x^7 + 1 \pmod{7}$$

✅ Identity holds → Prime

---

Example 2: $n = 9$ (Composite)

$$(x + 1)^9 = x^9 + 9x^8 + 36x^7 + \cdots + 1$$

Modulo $9$:

$$36x^7 \not\equiv 0 \pmod{9}$$

❌ Identity fails → Composite

---

Example 3: Carmichael Number $n = 561$

• Fermat test fails to detect composite

• AKS polynomial test detects composite

✔️ This is a major strength of AKS.

---

7. Time Complexity

• Original AKS:

  $$O((\log n)^{12})$$
  

• Improved versions:

  $$O((\log n)^6)$$
  

📌 Polynomial in number of digits of $n$

---

8. Comparison with Other Primality Tests

Test	Deterministic	Time	Error
Trial Division	Yes	Exponential	None
Fermat	No	Fast	High
Miller–Rabin	No	Very fast	Negligible
AKS	Yes	Polynomial	None

Why AKS Matters

• It is the first deterministic polynomial-time primality test

• It proves that PRIMES ∈ P

• It combines number theory and algebra in an elegant way

• Although not used in practice due to speed, it is a landmark theoretical result

---

Conclusion

The AKS algorithm stands as a milestone in theoretical computer science. While faster probabilistic tests are preferred in practical applications, AKS provides a mathematically rigorous and deterministic method for primality testing, demonstrating that prime numbers can be identified efficiently and conclusively.

AKS Primality Testing Algorithm – Pseudocode

---

Algorithm: AKS(n)

Input: Integer $n > 1$
Output: PRIME or COMPOSITE

---

AKS(n)
1. If n ≤ 1
       return COMPOSITE

2. If n = a^b for integers a > 1, b > 1
       return COMPOSITE

3. Find the smallest integer r such that
       ord_r(n) > (log n)^2

4. For a = 2 to r
       if gcd(a, n) > 1 and gcd(a, n) < n
            return COMPOSITE

5. If n ≤ r
       return PRIME

6. Let limit = ⌊ √φ(r) · log n ⌋

7. For a = 1 to limit
       if (x + a)^n ≠ x^n + a  (mod n, x^r − 1)
            return COMPOSITE

8. return PRIME

---

Explanation of Steps (Short – Exam Friendly)

1. Perfect power check eliminates obvious composites.

2. Finding r ensures polynomial-time execution.

3. GCD check detects small factors.

4. Polynomial congruence test verifies primality deterministically.

5. If all checks pass, n is prime.

---

Key Formula to Remember (Very Important)

$$n \text{ is prime } \iff (x + a)^n \equiv x^n + a \pmod{(n,\; x^r - 1)}$$

---

Time Complexity 

$$O((\log n)^6) \quad \text{(improved AKS)}$$

Python Code

import math

from math import gcd

from sympy.ntheory import totient

# ---------- Euler's Totient Function or use totient function from sympy----------

def phi(n):

    result = n

    p = 2

    temp = n

    while p * p <= temp:

        if temp % p == 0:

            while temp % p == 0:

                temp //= p

            result -= result // p

        p += 1

    if temp > 1:

        result -= result // temp

    return result

# ---------- Check Perfect Power ----------

def is_perfect_power(n):

    for b in range(2, int(math.log2(n)) + 1):

        a = int(round(n ** (1 / b)))

        if a ** b == n:

            return True

    return False

# ---------- Multiplicative Order ----------

def multiplicative_order(n, r):

    if gcd(n, r) != 1:

        return -1

    k = 1

    mod = n % r

    while mod != 1:

        mod = (mod * n) % r

        k += 1

    return k

# ---------- Find r ----------

def find_r(n):

    max_k = math.log2(n) ** 2

    r = 2

    while True:

        if gcd(n, r) == 1:

            if multiplicative_order(n, r) > max_k:

                return r

        r += 1

# ---------- Polynomial Multiplication ----------

def multiply_poly(p1, p2, mod_n, r):

    result = [0] * r

    for i in range(r):

        for j in range(r):

            result[(i + j) % r] += p1[i] * p2[j]

            result[(i + j) % r] %= mod_n

    return result

# ---------- Polynomial Congruence Test ----------

def poly_congruence(n, r, a):

    poly = [0] * r

    poly[0] = a

    poly[1] = 1   # x + a

    result = [1] + [0] * (r - 1)

    base = poly

    exp = n

    while exp > 0:

        if exp % 2 == 1:

            result = multiply_poly(result, base, n, r)

        base = multiply_poly(base, base, n, r)

        exp //= 2

    expected = [0] * r

    expected[0] = a

    expected[n % r] = 1

    return result == expected

# ---------- AKS Main Function ----------

def AKS(n):

    if n <= 1:

        return False

    # Step 1: Perfect power check

    if is_perfect_power(n):

        return False

    # Step 2: Find suitable r

    r = find_r(n)

    # Step 3: GCD check

    for a in range(2, r + 1):

        g = gcd(n, a)

        if 1 < g < n:

            return False

    # Step 4

    if n <= r:

        return True

    # Step 5: Polynomial congruence

    limit = int(math.sqrt(phi(r)) * math.log2(n))

    for a in range(1, limit + 1):

        if not poly_congruence(n, r, a):

            return False

    return True

print(AKS(561))

print(AKS(101))