Supervised by Dan Evans

Primes, Polynomials and Polynomial Time


“The problem of distinguishing prime numbers from composite numbers and of resolving the latter into their prime factors is known to be one of the most important and useful in arithmetic…

Further, the dignity of the science itself seems to require that every possible means be explored for the solution of a problem so elegant and so celebrated…”

C. F. Gauss, Disquisitiones Arithmeticae (1801)


If Gauss thought something was so important, then it’s surely worth looking at! The advent of modern day communication and cryptography techniques has given this even more practical relevance in ways Gauss could never have imagined. As a consequence, finding efficient ways to detect primality and to factorise integers is as important as ever. In this project, we will focus mainly on the first half of the problem: how to determine if a given number is prime.

Primality tests occur in various different flavours.

There is a common theme running through many tests going back to Lucas: given an integer, construct a group which is so large that it forces the integer to be prime. He was able to use this idea to confirm the \(39\) digit number \(2^{127}-1\) is prime by hand, and it is said it took him \(19\) years to manage this! By contrast, with massive amounts of computer power available these days, the largest known prime \(2^{136,279,841}-1\) discovered just this year has more than \(40\) million digits. On the other hand, for numbers which don’t have a special shape we can exploit, the best deterministic algorithms we have at the moment can reach numbers with tens of thousands of decimal digits, but not much beyond.

We will investigate the long history and mathematics behind primality testing, applying and strengthening concepts learnt in Elementary Number Theory II and Algebra II. We can also introduce more advanced ideas involving elliptic curves and cyclotomic fields which lead to some of the fastest known general tests.

Along the way, we will discuss relevant aspects of computational complexity theory, which give a measure of how fast an algorithm is, depending on the integer input size. 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 number of arithmetic operations in the algorithm is bounded above by 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.

We can also look beyond primality testing into related areas of computational number theory. The second half of Gauss’s problem to factorise composite integers, is an enormous subject which involves some very deep mathematics for the best methods, but we can venture into some of the preliminary ideas.


Prerequisites and Corequisites

Elementary Number Theory II and Algebra II are necessary prerequisites. The topic uses group theory and modular arithmetic concepts in essential ways.

Cryptography+Codes III is a necessary corequisite. The Cryptography half of this module contains some specific concepts such as elliptic curves, as well as motivating why we might care about primality and factorising very large numbers.

Also, Number Theory III or Galois Theory III could be useful, depending on the direction you choose.


References

There are many webpages and online articles discussing prime numbers and primality tests. A few are:

There are also many textbooks discussing computational number theory and primality tests, with recent ones including discussions of the AKS algorithm:


Contact details

If you have any questions, feel free to drop me a message at daniel.evans@durham.ac.uk