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.