Project Topic: Deterministic Primality Testing
Until recently, there was no known easy deterministic algorithm
(i.e., an algorithm with no random steps, and with no possibility of
false positives) for testing whether a given number is prime.
Here you are to research the AKS algorithm for deterministic
primality testing. Ideally, this project has three parts.
- A presentation of the algorithm, together with a proof that it is
correct (that it answers yes if and only if the input is prime) and a proof that it is easy (that it runs in time
log(N)k for some small exponent k, on input N). You should strive to produce
a writeup that is as self-contained and elementary as possible, even at the sacrifice of
presenting the most efficient version of the algorithm. I suggest looking up the article by
Andrew Granville in the Bulletin of the American Mathematical Society.
- An implementation of the algorithm. (It is easy to find
implementations on the Internet---I want you to carry through your own
implementation, together with a careful description of what you are
doing, even if it is much sloppier and less efficient than polished
implementations.
- Experimental comparison of running times with probabilistic
primality testing (Miller-Rabin test). Miller-Rabin will surely be faster, but I want
you to quantify this carefully. How large an integer can you comfortably test for primality
with your AKS implementation?
Python might be a poor choice for testing large integers because it is rather slow
. But it could be useful for hacking together something
that you can test on relatively small inputs. I suggest
using the BigInteger class in Java instead, but you might have another
programming environment you prefer.