Primality Testing for Beginners (Student Mathematical Library)

How can you tell whether a number is prime? What if the number has hundreds or thousands of digits? This question may seem abstract or irrelevant, but in fact, primality tests are performed every time we make a secure online transaction. In 2002, Agrawal, Kayal, and Saxena answered a long-standing open question in this context by presenting a deterministic test (the AKS algorithm) with polynomial running time that checks whether a number is prime or not. What is more, their methods are essentially elementary, providing us with a unique opportunity to give a complete explanation of a current mathematical breakthrough to a wide audience. Rempe-Gillen and Waldecker introduce the aspects of number theory, algorithm theory, and cryptography that are relevant for the AKS algorithm and explain in detail why and how this test works. This book is specifically designed to make the reader familiar with the background that is necessary to appreciate the AKS algorithm and begins at a level that is suitable for secondary school students, teachers, and interested amateurs. Throughout the book, the reader becomes involved in the topic by means of numerous exercises Cover 1 Title page 4 Contents 8 Preface 12 Introduction 14 Part I. Foundations 24 Natural numbers and primes 26 Algorithms and complexity 56 Foundations of number theory 96 Prime numbers and cryptography 142 Part II. The AKS algorithm 164 The starting point: Fermat for polynomials 166 The theorem for Agrawal, Kayal, and Saxena 182 The algorithm 196 Open questions 206 Solutions and comments to important exercises 220 Bibliography 246 List of symbols 250 Index 252 Back Cover 258