Uncertainty can be Better than Certainty: Some Algorithms for Primality Testing

For many years mathematicians and computer scientists have searched for a fast and reliable primality test. This is especially relevant nowadays, because the popular RSA public-key cryptosystem requires very large primes in order to generate secure keys. I will describe some efficient randomised algorithms that are useful, but have the defect of occasionally giving the wrong answer, or taking a very long time to give an answer.

In 2002, Agrawal, Kayal and Saxena (AKS) found a deterministic polynomial-time algorithm for primality testing. I will describe the original AKS algorithm and some improvements by Bernstein and Lenstra. As far as theory is concerned, we now know that "PRIMES is in P", and this appears to be the end of the story. However, I will explain why it is preferable to use randomised algorithms in practice.