Edouard Lucas and Primality Testing

by Williams, Hugh C.

• ISBN13: 9780471148524
• ISBN10: 0471148520
• Edition: 1st
• Format: Hardcover
• Copyright: 1998-03-31
• Publisher: Wiley-Interscience

Summary

Describes the development and extension of fundamental idea of Edouard Lucas, a French mathematician and mathematical recreationist, that is still used today in the verification of the largest primes.

Author Biography

Hugh Cowie Williams is a Canadian mathematician. He deals with number theory and cryptography.

Table of Contents

Table of symbols	ix	(4)
Preface	xiii
1 Preliminaries	1	(26)
1.1 Results from elementary number theory	1	(6)
1.2 Algorithms and complexity	7	(5)
1.3 Continued fractions	12	(4)
1.4 Some arithmetic functions	16	(2)
1.5 Results concerning binomial congruences	18	(6)
Notes for Chapter 1	24	(3)
2 The Beginnings	27	(26)
2.1 Antiquity	27	(3)
2.2 From the Middle Ages to Mersenne	30	(5)
2.3 Fermat and Euler	35	(5)
2.4 Lagrange, Legendre, and Gauss	40	(4)
2.5 The early tablemakers	44	(3)
Notes for Chapter 2	47	(6)
3 Lucas' Early Work	53	(16)
3.1 Lucas' earliest primality tests	53	(5)
3.2 Lucas and M(127)	58	(7)
Notes for Chapter 3	65	(4)
4 The Lucas Functions	69	(28)
4.1 Definition of the Lucas functions	69	(4)
4.2 Identity properties of the Lucas functions	73	(10)
4.3 Arithmetic properties	83	(7)
4.4 Computation of the Lucas functions	90	(3)
Notes for Chapter 4	93	(4)
5 Lucas' Tests	97	(24)
5.1 Lucas' early tests for Mersenne primes	97	(2)
5.2 The Fermat numbers	99	(3)
5.3 Landry and F(6)	102	(5)
5.4 Lucas and necessity	107	(7)
5.5 Lucas' extended tests	114	(3)
Notes for Chapter 5	117	(4)
6 Later Developments	121	(20)
6.1 The work of Proth and Pocklington	121	(4)
6.2 Early factoring methods	125	(7)
6.3 Cole's example	132	(1)
6.4 The Fermat numbers	133	(5)
Notes for Chapter 6	138	(3)
7 Early Devices	141	(32)
7.1 The beginnings of mechanization	141	(4)
7.2 Mechanisms for testing Mersenne numbers	145	(11)
7.3 The number sieve	156	(13)
Notes for Chapter 7	169	(4)
8 Kraitchik and Lehmer	173	(32)
8.1 Kraitchik	173	(7)
8.2 D.H. Lehmer	180	(9)
8.3 Some special numbers	189	(7)
8.4 The Lehmer functions	196	(3)
8.5 Some tables	199	(2)
Notes for Chapter 8	201	(4)
9 Finite Fields	205	(26)
9.1 Groups and rings	205	(5)
9.2 Polynomials and fields	210	(9)
9.3 Finite fields	219	(4)
9.4 Some polynomial congruences	223	(7)
Notes for Chapter 9	230	(1)
10 Lucas' Functions Generalized	231	(26)
10.1 A generalization of the Lucas functions	231	(5)
10.2 Some identity properties	236	(4)
10.3 Some arithmetic properties	240	(8)
10.4 Some results on C(n)	248	(4)
10.5 Primality tests	252	(3)
Notes for Chapter 10	255	(2)
11 Special Tests for Primality	257	(28)
11.1 Gauss and Jacobi sums	257	(10)
11.2 A primality test	267	(5)
11.3 Some special cases	272	(10)
Notes for Chapter 11	282	(3)
12 The Influence of the Computer	285	(32)
12.1 Some observations	285	(5)
12.2 Some primality tests	290	(7)
12.3 Some further tests	297	(9)
12.4 A result of Lenstra and R(1031)	306	(7)
Notes for Chapter 12	313	(4)
13 Results from the Computer	317	(26)
13.1 The Cunningham project	317	(4)
13.2 Primes of the form k2(n) + 1	321	(5)
13.3 Fast multiplication	326	(6)
13.4 Fermat and Mersenne numbers	332	(6)
Notes for Chapter 13	338	(5)
14 Primality Proofs	343	(28)
14.1 Factoring and primality tests	343	(3)
14.2 The complexity of primality testing	346	(5)
14.3 Certificates of primality	351	(6)
14.4 Introduction to elliptic curves	357	(4)
14.5 Very short certificates of primality	361	(6)
Notes for Chapter 14	367	(4)
15 Probabilistic Primality Tests	371	(34)
15.1 Pseudoprimes and Carmichael numbers	371	(5)
15.2 Stronger pseudoprimes	376	(9)
15.3 Cryptography	385	(7)
15.4 Probabilistic methods	392	(6)
Notes for Chapter 15	398	(7)
16 Recent Sieve Devices	405	(26)
16.1 Modern sieve devices	405	(7)
16.2 Pseudosquares and primality testing	412	(5)
16.3 The search for pseudosquares	417	(6)
16.4 Application to testing primality	423	(5)
Notes for Chapter 16	428	(3)
17 Primality Proving Today	431	(38)
17.1 The APR test	431	(4)
17.2 The Jacobi sums test	435	(9)
17.3 Primality testing with elliptic curves	444	(6)
17.4 The Lucas connection	450	(12)
17.5 Conclusion	462	(2)
Notes for Chapter 17	464	(5)
Bibliography	469	(46)
Index	515