Determining whether a number is prime or composite is a task that mathematicians have struggled with for centuries. In 1801, Gauss called the problem “one of the most important and useful in arithmetic”. The advent of modern day communication and cryptography techniques has given this a more practical relevance, and finding efficient primality tests is as important as ever.
Primality tests occur in various different flavours - some are deterministic, others have a probabilistic element, some work for arbitrary numbers, others work for integers of particular shapes such as Mersenne numbers of the form \(2^m-1\). The best deterministic algorithms at the moment can (with a lot of computing power and time) reach general numbers with \(30,000\) to \(40,000\) digits. On the other hand, the largest known prime \(2^{82589933}-1\) has nearly \(25\) million decimal digits.
A relatively recent surprise in this area is the AKS algorithm, discovered in 2002 by Agrawal, Kayal and Saxena, two of whom were undergraduates at the time. This uses the arithmetic of polynomials modulo \(n\) to determine if \(n\) is prime in polynomial time, meaning that the time taken by the algorithm is at worst a polynomial in the number of digits of \(n\). Whilst this test has important theoretical significance, there are many other algorithms available that are worse in theory but better in practice.
In this project, we will investigate the long history and mathematics behind primality tests. In particular, we will apply and strengthen concepts learnt in Elementary Number Theory II and Algebra II, discuss relevant aspects of computational complexity theory, leading to recent developments such as tests involving elliptic curves, cyclotomic fields and the AKS algorithm. We can also go beyond this to venture into related areas of computational number theory, such as the parallel problem of factorising composite integers.
Elementary Number Theory II and Algebra II are essential, as is the 3rd year module Cryptography+Codes III. Also, Number Theory III or Galois Theory III could be useful, depending on the direction you choose.
There are many webpages and online articles discussing prime numbers and primality tests. A few are:
A nice talk and article by Carl Pomerance describing a theme running through many primality tests going back to Lucas: given an integer, construct a group which is so large that it forces the integer to be prime.
A blogpost by Terry Tao on the AKS algorithm.
The PrimePages website contains lots of information about prime records as well as giving an overview of a number of primality tests.
There are also many textbooks discussing computational number theory and primality tests, with recent ones including discussions of the AKS algorithm:
Prime Numbers: A Computational Perspective ( library link ) by Crandall and Pomerance is an excellent book covering a huge amount of relevant material.
A Computational Introduction to Number Theory and Algebra ( library link ) by Victor Shoup. This book is freely available at this webpage and the latest edition includes the AKS test.
Arithmetics ( library link ) by Marc Hindry.
Primality Testing in Polynomial Time by M. Dietzfelbinger.
Primality Testing for Beginners ( library link ) by Rempe-Gillen & Valdecker.
If you have any questions, feel free to drop me a message at daniel.evans@durham.ac.uk