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.