Primality Testing for Beginners

Primality Testing for Beginners is an undergraduate-level mathematics book on primality tests, methods for testing whether a given number is a prime number, centered on the AKS primality test, the first method to solve this problem in polynomial time. It was written by Lasse Rempe-Gillen and Rebecca Waldecker, and originally published in German as Primzahltests für Einsteiger: Zahlentheorie, Algorithmik, Kryptographie (Vieweg+Teubner, 2009). It was translated into English as Primality Testing for Beginners and published in 2014 by the American Mathematical Society, as volume 70 of their Student Mathematical Library book series. A second German-language edition was publisher by Springer in 2016.

Topics

Primality Testing for Beginners has six chapters, divided into two parts: four chapters on background material in number theory and computational complexity theory, and three on the AKS primality test.

Chapter 1 includes basic material on number theory, including the fundamental theorem of arithmetic on unique factorization into primes, the binomial theorem, the Euclidean algorithm for greatest common divisors, and the sieve of Eratosthenes for generating the sequence of prime numbers. Chapter 2 begins the study of algorithms and their complexity, including algorithms for basic computations in arithmetic, the notion of computability, polynomial-time algorithms, randomization, and nondeterministic polynomial time. In randomized algorithms, it introduces the distinction between Las Vegas algorithms that always return the correct answer after a random amount of time (such as quicksort) and Monte Carlo algorithms for which there is a small probability of getting a wrong answer (exemplified by algorithms based on the Schwartz–Zippel lemma for polynomial identity testing). Chapter 3 provides additional material in number theory, including the Chinese remainder theorem, Fermat's little theorem, and the Fermat primality test based on it. It also introduces calculation with polynomials and with modular arithmetic. The first part of the book concludes with chapter 4, on the history of prime numbers and primality testing, including the prime number theorem (in a weakened form), applications of prime numbers in cryptography, and the widely used Miller–Rabin primality test, which runs in randomized polynomial time.

Chapter 5 generalizes Fermat's little theorem from numbers to polynomials, and introduces a randomized primality test based in this generalization. Chapter 6 provides the key mathematical results behind the correctness of the AKS primality test, and chapter 7 describes the test itself. Both the correctness and the polynomial running time of the algorithm are proven rigorously. Exercises are included in each chapter, and a section at the end of the book provides answers to some of them. Another appendix lists some unsolved problems from number theory.

Audience and reception

Although primarily for undergraduate students of mathematics, Primality Testing for Beginners requires very little background knowledge, and may also be suitable for advanced secondary school students. It is based on a summer program for students at this level, run by the authors in Germany with the goal of introducing the students to recent research.

Reviewers Robin Chapman and Jeffrey Ehme agree that the overall content of the book is probably too slight to use it as the main textbook for an undergraduate number theory course, but that it could be a good supplement for such a course, or for a course in cryptography. Reviewer Frederic Green recommends it as a good introduction to mathematical research more generally, and also suggests its use by researchers as a quick reference on primality testing.