## AKS Primality Prover, Part 2

### October 5, 2012

In the previous exercise we wrote some auxiliary functions needed for the implementation of the AKS primality prover. Today we will implement the AKS algorithm:

AKS Primality Prover: Given an integer

n> 1, determine if it is prime or composite.

1. Ifn=afor integers^{b}a> 0 andb> 1, output COMPOSITE.

2. Find the smallestrsuch that ord_{r}(n) > (log_{2}n)^{2}.

3. If 1 < gcd(a,n) <nfor somea≤r, output COMPOSITE.

4. Ifn≤r, output PRIME.

5. For eachafrom 1 to floor √φ(r) · log_{2}n), if (x+a)^{n}&neq;x+^{n}a(modx− 1,^{r}n), output COMPOSITE.

6. Output PRIME.

Here ord_{r}(*n*) is the multiplicative order of *n* modulo *r*, both logarithms are to the base 2, φ(*r*) is Euler’s totient function, and the polynomial modular exponentiation is done as in the previous exercise.

Your task is to write a program to prove primality using the AKS algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

A version in Python. The multiplication of the polynomials and the division by

X^r – 1 is very slow. The division moves all amplitudes to position %r (the

amplitude of X^k goes to X^(k%r)). I made a faster version that uses library

numpy to do the polynomial mutliplication. Then all amplitudes for k >-= r are

moved to the range 0 – r-1.

For my original version the time needed for n=887 was 51 seconds. This version

needs 0.14 seconds

Paul, great job writing very straightforward code, and truly amazing speed out of Python by using numpy’s convolve. However by putting off the modulo until after the convolve and fold, it does restrict the usable range. For example, aks(190000003) returns False on my 64-bit machine. As I mentioned before, for smaller numbers it’s rocking fast and (more important) very readable complete code.