SCS Undergraduate Thesis Topics

2004-2005
Student Advisor(s) Thesis Topic
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.


Close this window