Programming Praxis

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³ + 4x² + 12x + 3 modulo (x⁵ − 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³ + 4x² + 12x + 3 squared is x⁶ + 8x⁵ + 40x⁴ + 102x³ + 168x² + 72x + 9. To reduce the result modulo x⁵ − 1 we divide using the grade-school long-division algorithm and take the remainder, which gives x + 8 with a remainder of 40x⁴ + 102x³ + 168x² + 73x + 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 6x⁴ + 0x³ + 15x² + 5x + 0. The whole computation can be organized as shown below. Note how the division and reduction modulo x⁵ − 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