SCS Undergraduate Thesis Topics
|Chris Rotella||Klaus Sutner||An Efficient Implementation of the AKS Polynomial-Time Primality Testing Algorithm|
In their "PRIMES is in P" paper, Agarwal, Kayal, and Saxena (2002) provided a deterministic, polynomial-time algorithm for testing a number for primality. My work focuses on determining the real-world performance of the AKS algorithm. Implementation issues are discussed in detail, and empirical results presented. The performance of AKS is compared to other primality testing algorithms such as sieving, trial divisions, and Rabin-Miller.