The Life of Primes in 37 Episodes

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\x27s 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. An infinite family -- The search for large primes -- The great insight of Legendre and Gauss -- Euler, the visionary -- Dirichlet's theorem -- The Bertrand postulate and the Chebyshev theorem -- Riemann shows the way -- Connecting the zeta function to the prime counting function -- The intriguing Riemann Hypothesis -- Mertens' theorems -- Counting the number of primes, from Meissel to today -- Hadamard and de la Vall'ee Poussin stun the world -- An elementary proof of 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 -- Establishing if a given integer is prime or not -- The Lucas and P'epin 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 -- The Fermat factorisation algorithm -- From the Germat factorisation algorithm to the quadratic sieve -- The Pollard p - 1 factorisation algorithm -- The Pollard Rho factorisation algorithm -- Two factorisation methods based on modern algebra -- Algebraic factorisation -- Measuring and comparing the speed of various algorithms -- Cryptography, from Julius Caesar to the RSA cryptosystem -- The present and future life of primes "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"--Provided by publisher 1/2 title 2 title 4 copyright 5 Contents 6 Preface 12 Part 1 16 Episode 1 18 Episode 2 22 Episode 3 28 Episode 4 32 Episode 5 40 Episode 6 46 Episode 7 56 Episode 8 60 Episode 9 66 Episode 10 72 Episode 11 76 Episode 12 84 Episode 13 94 Part 2 100 Episode 14 102 Episode 15 110 Episode 16 114 Episode 17 118 Episode 18 122 Episode 19 132 Episode 20 136 Episode 21 142 Episode 22 152 Part 3 156 Episode 23 158 Episode 24 164 Episode 25 170 Episode 26 174 Episode 27 180 Episode 28 184 Part 4 190 Episode 29 192 Episode 30 198 Episode 31 206 Episode 32 210 Episode 33 214 Episode 34 222 Episode 35 230 Part 5 236 Episode 36 238 Episode 37 246 Appendix A 262 Appendix B 268 Appendix C 320 Bibliography 328 Notation and Symbols 338 Index of short bios 340 Index of subjects 342