This is an old revision of the document!
Contact: Ghid Maatouk
Room: BC 128
Tel: 021-693-12-05
Email: ghid [dot] maatouk [at] epfl [dot] ch
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.