The Essentials of Primality Testing

Imagine that you have to determine whether a given one-hundred-digit odd natural number is prime. This task may sound like a bad joke in a mathematics class, but the answer is crucial for modern cryptography. A straightforward procedure would be to check, for every natural number $d$ greater than 1 and less than the square root of the given number $n$, whether $d$ divides $n$. This would require approximately 105010^{50}1050 division operations. Even if each such operation took only 1 nanosecond, we would be waiting for the answer for about 103310^{33}1033 years, which makes this approach inefficient.

An efficient procedure (or algorithm) is one that requires $p(\log n)$ operations, where $p(x)$ is a polynomial. Fortunately, in practice there exist very fast probabilistic algorithms, such as the Miller–Rabin test, which determine with high probability whether a number is prime. In this lecture, we will look at some of these procedures and the basic ideas behind them.

About the lecturer: Aleksander Simonič earned his PhD in analytic number theory in 2022 at the University of New South Wales (Australia). After completing his doctorate, he worked there as a researcher and lecturer, teaching various mathematics courses to students of the Australian Defence Force Academy. He is currently employed as an assistant at the Faculty of Mathematics, Natural Sciences and Information Technologies of the University of Primorska, where his research focuses on L-functions and where he teaches two number-theory courses. He is a passionate lover of classical music and long walks.