Programming Praxis

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. If n = a^b for integers a > 0 and b > 1, output COMPOSITE.
2. Find the smallest r such that ord_r(n) > (log₂ n)².
3. If 1 < gcd(a, n) < n for some a ≤ r, output COMPOSITE.
4. If n ≤ r, output PRIME.
5. For each a from 1 to floor √φ(r) · log₂ n), if (x + a)ⁿ &neq; xⁿ + a (mod x^r − 1, 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.

Pages: 1 2