Project III (MATH3382) 2021-22

Primes, Polynomials and Polynomial Time

Dan Evans

Description

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 computers and cryptography has given this a more practical relevance and finding efficient primality tests is as important as ever.

These 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 2m-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 282589933-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 various of these primality tests and related areas in computational number theory. 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, the AKS algorithm and beyond.


Prerequisites and Corequisites

Elementary Number Theory II and Algebra II are necessary. We will often be dealing with polynomials over finite fields and so Coding Theory and Cryptography III would be very useful, as well as for familiarity with elliptic curves.

Resources

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 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, some of which now include discussions of the AKS algorithm:

email: Dan Evans