Maria Francis-Moullier

Undergraduate Math Research Report

Spring 2003

 

            This project investigated the new primality testing algorithm outlined in the paper “Primes is in P”, authored by Indian mathematicians Manindra Agrawal, Neeraj Kayal and Nitin Saxena.  This algorithm, presented in 2002, is significant because it is both deterministic, meaning that the output is not based on probability, and hence there is no possibly of error, and also runs in polynomial time.  Previously, no such algorithm existed.

            There are many primality testing algorithms that have been developed by mathematicians during the centuries that this problem has been investigated.  The first known such algorithm is the “Sieve of Eratosthenes,” developed by the Greek mathematician, which consists of trial division up to the square root of the input.  While this algorithm is deterministic, it is extremely slow, taking exponential time, and quickly becomes impractical for large inputs.

            An important theorem relating to prime numbers and used in the AKS algorithm that I invested is Fermat’s Little Theorem.  This theorem states:

If n is a prime integer, than for any integer a which is relatively prime to n:

 

a(n-1) == 1 (mod n)

 

Clearly this theorem is very useful in primality testing, but it must be noted that while the test’s result is true for every prime, there are some composite numbers that also pass this test.

            There are countless other primality testing algorithms.  For example, an algorithm developed by G. L. Miller in 1976 fulfilled the requirements of being both deterministic and running in polynomial time, but it relied on the as yet unproven Extended Riemann Hypothesis.  M. O. Rabin modified Miller’s algorithm and created a randomized, polynomial time algorithm that ranks among the most commonly used.  Adleman, Pomerance and Rumely developed a test for primes that was deterministic and ran very close to polynomial time, but the solution still remained elusive.

            Agrawal, Kayal and Saxena based their work off another form of Fermat’s Little Theorem, one which reads:

Suppose that a and p are relatively prime integers with p > 1.  p is prime if and only if:

(x-a)p = (xp-a)   (mod p)

However, the number of comparisons needed for an algorithm based on that form of the theorem would be too great, so they based their test on a modification, specifically:

Suppose that a and p are relatively prime integers with p > 1, and r and p are relatively prime with r > 1.  There exists an r such that p is prime if and only if:

(x-a)p = (xp-a)   (mod xr - 1,p)

First they prove that such an r exists for every value of p greater than 1, and then go on  to outline a much more efficient algorithm.  In fact, with this modification as the crux of their paper, Agrawal, Kayal and Saxena were able to develop an algorithm that would be deterministic and run in polynomial time.

            My research project consisted of first understanding the algorithm, which took a significant portion of the semester, and then implementing the algorithm as a Java application.  The algorithm involves extremely large numbers for the coefficients of the polynomials.  Initially this caused me problems since the numbers were overflowing the capacity of primitive type Java integer representation.  Eventually I adopted an arbitrary-precision data type built into Java (the BigInteger class), which allowed the program to work.

After implementing a successful version of the code, I discovered that the program took an extremely long time to run, and so I went through two iterations of the code trying to improve the runtime.  The first iteration used the binomial expansion to take a binomial to a power, and the second iteration substituted successive squaring to attempt to improve the runtime.  The runtime was improved substantially, but the program is still quite slow.  I believe that a portion of this is simply due to the speed of the Java language, in addition to the large amount of computation that the algorithm requires.

Prime input (n)

Time for result – iteration 1 (sec.)

Time for result – iteration 2 (sec.)

31

8.00

7.04

71

18.29

13.50

127

43.08

24.63

181

98.57

50.37

This table shows the runtime differences between Iteration 1 and Iteration 2 on a 900 Mhz Pentium III with 512 MB of RAM

            As a continuation of this project, I would like to implement the algorithm in the C programming language, which I believe would be both natively faster, and allow me access to bitwise operations that would let me optimize the code further.  Also, there are still improvements to the algorithm itself that I did not have time to implement, and would be interesting to study.