How is the AKS primality test Rosetta code so simple

algorithmscomputational complexitycomputer scienceprimality-testprime numbers

Skip to the end to see alternative question.

The following is a Python implementation of the AKS Primality Test.

from sympy import *

def expand_x_1(n): 
    # This version uses a generator and thus less computations
    c = 1
    for i in range(n//2 + 1):       # // means flooring after divide
        c = c*(n - i)//(i + 1)
        yield c

def aks(p):
    if p==2:
        return True

    for i in expand_x_1(p):
        if i % p:
            # we stop without computing all possible solutions
            return False
    return True


for n in range(2, 10000):
    primality = aks(n)
    primality1 = isprime(n)
    if primality != primality1:
        print("Fails @", n)  # Never prints
        assert (0)
    else:
        print(primality)

How is it possible that they took that much more in-depth pseudocode of the algorithm (that involves polynomial operations), and converted it into this 10-line version?

Is the above really the AKS primality test? I got it from:

https://rosettacode.org/wiki/AKS_test_for_primes#Python

Let the input be called $n$, not $p$.

The code in expand_x_1(n) must be computing:

$$c_0 = 1, c_i = \lfloor \dfrac{c_{i-1}(n-i)}{i + 1}\rfloor$$

Where $c_i = $ the $i$th yielded value. The other code using this value simply tests whether $c_i \neq 0 \pmod n$, in which case (if true) it returns False for composite. Else if for all $c_i$ values at $i = 0..\lfloor \dfrac{n}{2} \rfloor + 1$ we have $c_i = 0 \pmod n$, then True is returned.

The recursion plus this test don't seem at all like what makes up the AKS algorithm. So I was hoping an analytic number theorist could explain the formula.

Alternatively, if you can't answer the above, then:

How can we study the formula for $c_i$; can you think of any rearrangments it has? Such as maybe the denominators combining across recursive subcalls that have floor etc.

This is so I don't have to open up another question regarding this formula.

For example, I modified the code to:

def expand_x_1(n): 
   c = 1
   d = 1
   for i in range(n//2 + 1):
       d *= (i + 1)
       c = c*(n - i)
       yield c//d

Therefore, since it's getting no failures when I run it, I can somewhat safely assume that "denominators can be combined" algebraically, i.e. there is some
identity made use of that derives from the basic properties of floor.

What else can we say and how does this formula relate to polynomial arithmetic?

Best Answer

The numbers you’ve labelled as $c_i$ are the binomial coefficients $\binom ni$; the code checks whether $\binom ni \equiv 0 \pmod n$ for all $0 < i \le \frac n2$. This is not the AKS algorithm. It’s the exponential-time brute force algorithm listed in the Wikipedia article to motivate the AKS algorithm.

Related Question