Taken by: Monica Perrenoud
Completed by: Monica Perrenoud
In this project, you will learn about primality testing, that is, the problem of determining whether a given number is a prime. For many years, it was not known whether this problem had a deterministic polynomial-time algorithm, but in 2004, Agrawal, Kayal and Saxena gave such an algorithm for primality testing in their paper “Primes is in P”.
The project involves understanding and implementing a well-known and efficient randomized algorithm, the Rabin-Miller primality testing algorithm, and understanding the deterministic AKS algorithm.
Prerequisites: algebra and basic number theory.