---- dataentry project ----
title : Randomized and Deterministic Primality Testing
contactname: Ghid Maatouk
contactmail_mail: ghid.maatouk@epfl.ch
contacttel: 021-693-12-05
contactroom: BC 128
type : bachelor semester
state : completed
created_dt : 2009-06-08
taken_dt :  2009-06-15
completed_dt : 2010-01-13
by : Monica Perrenoud
output_media : 
table : projects
======
template:datatemplates:project
----

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.

{{:en:projects:bachelor_semester:randomized_and_deterministic_primality_testing.pdf|Randomized and Deterministic Primality Testing}}