|
|
|
ix | (4) |
| Preface |
|
xiii | |
|
|
|
1 | (26) |
|
1.1 Results from elementary number theory |
|
|
1 | (6) |
|
1.2 Algorithms and complexity |
|
|
7 | (5) |
|
|
|
12 | (4) |
|
1.4 Some arithmetic functions |
|
|
16 | (2) |
|
1.5 Results concerning binomial congruences |
|
|
18 | (6) |
|
|
|
24 | (3) |
|
|
|
27 | (26) |
|
|
|
27 | (3) |
|
2.2 From the Middle Ages to Mersenne |
|
|
30 | (5) |
|
|
|
35 | (5) |
|
2.4 Lagrange, Legendre, and Gauss |
|
|
40 | (4) |
|
2.5 The early tablemakers |
|
|
44 | (3) |
|
|
|
47 | (6) |
|
|
|
53 | (16) |
|
3.1 Lucas' earliest primality tests |
|
|
53 | (5) |
|
|
|
58 | (7) |
|
|
|
65 | (4) |
|
|
|
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) |
|
|
|
93 | (4) |
|
|
|
97 | (24) |
|
5.1 Lucas' early tests for Mersenne primes |
|
|
97 | (2) |
|
|
|
99 | (3) |
|
|
|
102 | (5) |
|
|
|
107 | (7) |
|
5.5 Lucas' extended tests |
|
|
114 | (3) |
|
|
|
117 | (4) |
|
|
|
121 | (20) |
|
6.1 The work of Proth and Pocklington |
|
|
121 | (4) |
|
6.2 Early factoring methods |
|
|
125 | (7) |
|
|
|
132 | (1) |
|
|
|
133 | (5) |
|
|
|
138 | (3) |
|
|
|
141 | (32) |
|
7.1 The beginnings of mechanization |
|
|
141 | (4) |
|
7.2 Mechanisms for testing Mersenne numbers |
|
|
145 | (11) |
|
|
|
156 | (13) |
|
|
|
169 | (4) |
|
|
|
173 | (32) |
|
|
|
173 | (7) |
|
|
|
180 | (9) |
|
|
|
189 | (7) |
|
|
|
196 | (3) |
|
|
|
199 | (2) |
|
|
|
201 | (4) |
|
|
|
205 | (26) |
|
|
|
205 | (5) |
|
9.2 Polynomials and fields |
|
|
210 | (9) |
|
|
|
219 | (4) |
|
9.4 Some polynomial congruences |
|
|
223 | (7) |
|
|
|
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) |
|
|
|
252 | (3) |
|
|
|
255 | (2) |
|
11 Special Tests for Primality |
|
|
257 | (28) |
|
11.1 Gauss and Jacobi sums |
|
|
257 | (10) |
|
|
|
267 | (5) |
|
|
|
272 | (10) |
|
|
|
282 | (3) |
|
12 The Influence of the Computer |
|
|
285 | (32) |
|
|
|
285 | (5) |
|
12.2 Some primality tests |
|
|
290 | (7) |
|
|
|
297 | (9) |
|
12.4 A result of Lenstra and R(1031) |
|
|
306 | (7) |
|
|
|
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) |
|
|
|
326 | (6) |
|
13.4 Fermat and Mersenne numbers |
|
|
332 | (6) |
|
|
|
338 | (5) |
|
|
|
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) |
|
|
|
367 | (4) |
|
15 Probabilistic Primality Tests |
|
|
371 | (34) |
|
15.1 Pseudoprimes and Carmichael numbers |
|
|
371 | (5) |
|
15.2 Stronger pseudoprimes |
|
|
376 | (9) |
|
|
|
385 | (7) |
|
15.4 Probabilistic methods |
|
|
392 | (6) |
|
|
|
398 | (7) |
|
|
|
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) |
|
|
|
428 | (3) |
|
17 Primality Proving Today |
|
|
431 | (38) |
|
|
|
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) |
|
|
|
462 | (2) |
|
|
|
464 | (5) |
| Bibliography |
|
469 | (46) |
| Index |
|
515 | |
