Algorithms for Testing Primality

Abstract

Large prime numbers are very important in modern-day information security. To find such large prime numbers, algorithms which can efficiently determine primality for large numbers are needed. Beginning with one of the oldest and most well-known primality testing algorithms, we discuss several ways in which more efficient algorithms can be derived. Some of the algorithms we will look at are probabilistic, in the sense that they will determine a number as ``probably prime''. However, assuming a very deep hypothesis in mathematics, we can construct efficient deterministic variants of these probabilistic algorithms. We conclude our theoretical discussion of primality testing algorithms with an algorithm which was discovered at the beginning of this century in one of the biggest breakthroughs in primality testing, since it provides an efficient deterministic method to test for primality without relying on any unproven assumptions. We complement the theoretical discussion with a short practical analysis of the different algorithms presented, where we will see that several of the algorithms perform much more efficient in practice than what has been theoretically proven.