William (Alex) Toussaint
Research Proposal for Summer 2004
Advisor: Cetin Urtis
Project: Construction of an Efficient Computer Primality-Testing Algorithm
After the recent development of public key cryptography, primality testing of large numbers has become an increasingly important topic of research. In 2002, Agrawal, Kayal and Saxena proposed an algorithm (called the “AKS test”) which produces a proof of primality or compositeness in polynomial time. This algorithm was a major breakthrough, because although previous algorithms existed which could be used to test numbers for primality, they took longer than polynomial time to run.
The AKS Test is based on the fact that if a and n are relatively prime, then
. The AKS test basically consists of numerous evaluations of this polynomial for different values of a. To save time, the congruence is evaluated modulo a polynomial of the form xr-1, where r has certain properties and is determined in polynomial time by the algorithm. If the congruence is satisfied for all values of a in the interval [1,], then n is proven to be prime. If not, then n is composite.
In 2003, Bernstein proposed several improvements to the AKS test, which greatly reduce the amount of running time required. For my summer research project, I will first read and understand the basic AKS test, including the theorems in which it is based. I will then attempt to implement an improved AKS algorithm, using the PARI/GP computer algebra system. PARI is based on the computer language C and is specifically written for calculations in number theory, and is very fast and efficient at these calculations. GP is the name of the scripting language used with PARI, which provides easy access to PARI’s commands.
Should I complete a working implementation of this improved test, the remaining research time will be spent looking at elliptic curves and their applications to primality testing. However, the improved AKS algorithm will be my main topic of research. I am tentatively planning to spend the first two months of the summer working on this project. The sources that I have found so far to start my research from are shown below.
Agrawal, M.; Kayal, N.; and Saxena, N. "Primes is in P." http://www.cse.iitk.ac.in/primality.pdf.
Bernstein D. J. "Proving Primality After Agrawal-Kayal-Saxena."
Weisstein, Eric W. "AKS Primality Test – From MathWorld”. http://mathworld.wolfram.com/AKSPrimalityTest.html.