## AKS Primality Prover, Part 1

### October 2, 2012

In the previous exercise, we looked at Pocklington’s algorithm for proving the primality of a number *n*; the algorithm depends on at least a partial factorization of *n*−1. In today’s exercise we look at an algorithm of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena of the Indian Institute of Technology in Kanpur, which does not rely on *n* to be of any special form, is purely deterministic, of provable polynomial time, not conditional on the Riemann Hypothesis, and unfortunately very slow.

The entire mathematical community was astonished in 2002 when Agrawal, Kayal and Saxena published their algorithm. In the first place, Kayal and Saxena were undergraduate students at the time; Agrawal was their professor. And in the second place, their proof is simple, not relying on any complicated math; the general reaction among mathematicians was “How could we have missed that? What else have we missed?” The three won numerous awards, and their algorithm has been thoroughly studied and analyzed.

We will look at the AKS algorithm in the next exercise. Today, we write two functions that will be needed to implement the AKS algorithm.

The first function computes the *multiplicative order* of *n* modulo *r*, written as ord_{r}(*n*), which is the smallest number *k* such that *n*^{k} ≡ 1 (mod *r*). The algorithm is straight forward: starting from *k* = 2, increment *k* until you find the answer. The multiplicative order exists only when *n* and *r* are co-prime.

The second function computes the modular exponentiation of a polynomial; it’s not hard to write, but requires some explanation. To compute the modular exponentiation of a polynomial is simple; it uses the same square-and-multiply algorithm that is used for the modular exponentiation of an integer, which is part of our Standard Prelude and is described in Algorithm 3.C of the essay Programming with Prime Numbers. All we need is the modular multiplication of two polynomials, which we will explain by example.

Consider the problem of squaring polynomial *x*^{3} + 4*x*^{2} + 12*x* + 3 modulo (x^{5} − 1, 17). Polynomial multiplication is exactly the same as grade-school multiplication, except there are no carries, so the process looks like this:

` 1 4 12 3`

1 4 12 3

--- --- --- ---

3 12 36 9

12 48 144 36

4 16 48 12

1 4 12 3

--- --- --- --- --- --- ---

1 8 40 102 168 72 9

Thus, *x*^{3} + 4*x*^{2} + 12*x* + 3 squared is *x*^{6} + 8*x*^{5} + 40*x*^{4} + 102*x*^{3} + 168*x*^{2} + 72*x* + 9. To reduce the result modulo *x*^{5} − 1 we divide using the grade-school long-division algorithm and take the remainder, which gives *x* + 8 with a remainder of 40*x*^{4} + 102*x*^{3} + 168*x*^{2} + 73*x* + 17:

` 1 8`

+ --- --- --- --- --- --- ---

1 0 0 0 0 -1 | 1 8 40 102 168 72 9

1 0 0 0 0 -1

--- --- --- --- --- ---

8 40 102 168 73 9

8 0 0 0 0 -8

--- --- --- --- --- ---

40 102 168 73 17

We can confirm the calculation by multiplying and adding the remainder:

` 1 0 0 0 0 -1`

1 8

--- --- --- --- --- ---

8 0 0 0 0 -8

1 0 0 0 0 -1

--- --- --- --- --- --- ---

1 8 0 0 0 -1 -8

40 102 168 73 17

--- --- --- --- --- --- ---

1 8 40 102 168 72 9

Then we simply reduce each of the coefficients of the remainder modulo 17, giving the result 6*x*^{4} + 0*x*^{3} + 15*x*^{2} + 5*x* + 0. The whole computation can be organized as shown below. Note how the division and reduction modulo *x*^{5} − 1 is accomplished, eliminating the high-order coefficients and adding them back to the low-order coefficients; we are relying here on the simple form of the polynomial modulus, and would have to do more work if it was more complicated:

` 1 4 12 3 multiplicand`

1 4 12 3 multiplier

--- --- --- ---

3 12 36 9 3 * 1 4 12 3 * x^0

12 48 144 36 12 * 1 4 12 3 * x^1

4 16 48 12 4 * 1 4 12 3 * x^2

1 4 12 3 1 * 1 4 12 3 * x^3

--- --- --- --- --- --- ---

1 8 40 102 168 72 9 1 4 12 3 * 1 4 12 3

-1 -8 1 8 reduce modulo x^5 - 1

--- --- --- --- --- --- ---

40 102 168 73 17 reduce modulo 17

6 0 15 5 0 final result

Your task is to write functions that compute the multiplicative order of *n* modulo *r* and the modular exponentiation of polynomials. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution in the comments below.

[…] Pages: 1 2 […]