Table of symbols Preface Preliminaries 1.1 Results from elementary number theory 1.2 Algorithms and complexity 1.3 Continued fractions 1.4 Some arithmetic functions 1.5 Results concerning binomial congruences Notes for Chapter 1 2 The Beginnings 2.1 Antiquity 2.2 From the Middle Ages to Mersenne 2.3 Fermat and Euler 2.4 Lagrange, Legendre, and Gauss 2.5 The early tablemakers Notes for Chapter 2 3 Lucas' Early Work 3.1 Lucas' earliest primality tests 3.2 Lucas and M127 Notes for Chapter 3 4 The Lucas Functions 4.1 Definition of the Lucas functions 4.2 Identity properties of the Lucas functions 4.3 Arithmetic properties 4.4 Computation of the Lucas functions Notes for Chapter 4 5 Lucas' Tests 5.1 Lucas' early tests for Mersenne primes 5.2 The Fermat numbers 5.3 Landry and F6 5.4 Lucas and necessity 5.5 Lucas' extended tests Notes for Chapter 5 Later Developments 6.1 The work of Proth and Pocklington 6.2 Early factoring methods 6.3 Cole's example 6.4 The Fermat numbers Notes for Chapter 6 Early Devices 7.1 The beginnings of mechanization 7.2 Mechanisms for testing Mersenne numbers 7.3 The number sieve Notes for Chapter 7 Kraitchik and Lehmer 8.1 Kraitchik 8.2 D.H. Lehmer 8.3 Some special numbers 8.4 The Lehmer functions 8.5 Some tables Notes for Chapter 8 9 Finite Fields 9.1 Groups and rings 9.2 Polynomials and fields 9.3 Finite fields 9.4 Some polynomial congruences Notes for Chapter 9 10 Lucas' Functions Generalized 10.1 A generalization of the Lucas functions 10.2 Some identity properties 10.3 Some arithmetic properties 10.4 Some results on Cn 10.5 Primality tests Notes for Chapter 10 11 Special Tests for Primality 11.1 Gauss and Jacobi sums 11.2 A primality test 11.3 Some special cases Notes for Chapter 11 12 The Influence of the Computer 12.1 Some observations 12.2 Some primality tests 12.3 Some further tests 12.4 A result of Lenstra and R1031 Notes for Chapter 12 13 Results from the Computer 13.1 The Cunningham project 13.2 Primes of the form k2n + 1 13.3 Fast multiplication 13.4 Fermat and Mersenne numbers Notes for Chapter 13 14 Primality Proofs 14.1 Factoring and primality tests 14.2 The complexity of primality testing 14.3 Certificates of primality 14.4 Introduction to elliptic curves 14.5 Very short certificates of primality Notes for Chapter 14 15 Probabilistic Primality Tests 15.1 Pseudoprimes and Carmichael numbers 15.2 Stronger pseudoprimes 15.3 Cryptography 15.4 Probabilistic methods Notes for Chapter 15 16 Recent Sieve Devices 16.1 Modern sieve devices 16.2 Pseudosquares and primality testing 16.3 The search for pseudosquares 16.4 Application to testing primality Notes for Chapter 16 17 Primality Proving Today 17.1 The APR test 17.2 The Jacobi sums test 17.3 Primality testing with elliptic curves 17.4 The Lucas connection 17.5 Conclusion Notes for Chapter 17 Bibliography Index