Keywords: number theory, prime numbers, algorithms

Prerequisites: (01018: Discrete Mathematics 2)

How do you check whether, say 73 is prime? You could try dividing with all primes greater than 1 and up to \(\sqrt{73} < 9\) and verify that none of them divides. This has the advantage of helping you *factor* 73 as well as answering the primality question. It has the disadvantage that if 73 was a much, much larger number, you would never finish the exciting task of testing potential divisors.

To the best of our current knowledge, it is much easier to *check* for primality, than it is to actually factor a number. Case in point: my computer algebra system answered within 1 second that \(10^{23423}+1\) is *not* prime, but it is still busy attempting to find a factorization.

This project is about those clever algorithms for primality testing. The famous, and shockingly simple, Rabin–Miller test is a *randomized* algorithm which can only prove non-primality: it answers either “definitely not prime” or “perhaps prime”. It works well for almost all non-primes, though, so it can usually be quite well trusted. The project might also touch upon the landmark paper of Agrawal et. al that can prove both primality and non-primality in polynomial time.

The project would involve implementing one or more of the investigated methods in a computer algebra system or a favourite programming language.