This book is about the life of primes. Indeed, once they are defined, primes take on a life of their own and the mysteries surrounding them begin multiplying, just like living cells reproduce themselves, and there seems to be no end to it. This monograph takes the reader on a journey through time, providing an accessible overview of the numerous prime number theory problems that mathematicians have been working on since Euclid. Topics are presented in chronological order as episodes. These include results on the distribution of primes, from the most elementary to the proof of the famous prime number theorem. The book also covers various primality tests and factorisation algorithms. It is then shown how our inability to factor large integers has allowed mathematicians to create today's most secure encryption method. Computer science buffs may be tempted to tackle some of the many open problems appearing in the episodes. Throughout the presentation, the human side of mathematics is displayed through short biographies that give a glimpse of the lives of the people who contributed to the life of primes. Each of the 37 episodes concludes with a series of problems (many with solutions) that will assist the reader in gaining a better understanding of the theory.
Jean-Marie De Koninck, Universite Laval, Quebec City, QC, Canada, and Nicolas Doyon, Universite Laval, Quebec City, QC, Canada
Counting primes, the road to the prime number theorem: An infinite family The search for large primes The great insight of Legendre and Gauss Euler, the visionary Dirichlet's theorem The Berstrand postulate and the Chebyshev theorem Riemannn shows the way Connecting the zeta function to the prime counting function The intriguing Riemann hypothesis Mertens' theorems Couting the number of primes, from Meissel to today Hadamard and de la Vallee Poussin stun the world An elementary proof of the prime number theorem Counting primes, beyond the prime number theorem: Sieve methods Prime clusters Primes in arithmetic progression Small and large gaps between consecutive primes Irregularities in the distribution of primes Exceptional sets of primes The birth of probabilistic number theory The multiplicative structure of integers Generalized prime number systems Is it a prime?: Establishing if a given integer is prime or not The Lucas and Pepin primality tests Those annoying Carmichael numbers The Lucas-Lehmer primality test for Mersenne numbers The probabilistic Miller-Rabin primality test The deterministic AKS primality test Finding the prime factors of a given integer: The Fermat factorisation algorithm From the Fermat factorisation algorithm to the quadratic sieve The Pollard $p$-1 factorisation algorithm The Pollard Rho factorisaction algorithm Two factorisation methods based on modern algebra Algebraic factorisation Measuring and comparing the speed of various algorithms Making good use of the primes and moving forward: Cryptography, from Julius Caesar to the RSA cryptosystem The present and future life of primes Appendix A. A time line of some key results on prime numbers Appendix B. Hints, sketches and solutions to a selection of problems Appendix C. Basic results from number theory, algebra and analysis Bibliography Notation and symbols Index of short biographies Index of subjects
