- Title: Primality tests
- Short description:
The object is to explore different methods for testing if a number is prime, among them the famous so called AKS primality test. This algorithm runs in time that is a polynomial in the length of the number being tested.
- Long description:
The problem of testing whether a given natural number is prime or composite has a long history. The oldest documented algorithm is the sieve method of Eratosthenes dating back to ancient Greece. About 2000 years later (in 2002) three Indian computer scientists, Agrawal, Kayal and Saxena, surpised many mathematicians and computer scientists by presenting an algorithm (called AKS) that tests primality of a number n in time that is polynomial in the number of digits in n.
The thesis project would be to understand their algorithm (which requires learning a bit about polynomial rings and their quotients) and to compare it to other methods. There are other algorithms that do not run in polynomial time, but nevertheless outperformes AKS on inputs sizes encountered in practice. There are also interesting probabilistic methods.
Depending on the interests of the student the work could put historical aspects, complexity theory or algebra more in focus.
- Contact: Anna Torstensson