|
Chapter 1 The Number of Primes Below a Given Limit |
|
|
|
|
1 | (1) |
|
The Fundamental Theorem of Arithmetic |
|
|
2 | (1) |
|
Which Numbers Are Primes? The Sieve of Eratosthenes |
|
|
2 | (2) |
|
General Remarks Concerning Computer Programs |
|
|
4 | (1) |
|
|
5 | (2) |
|
|
7 | (2) |
|
Hexadecimal Compact Prime Tables |
|
|
9 | (1) |
|
Difference Between Consecutive Primes |
|
|
9 | (1) |
|
The Number of Primes Below x |
|
|
10 | (2) |
|
|
12 | (1) |
|
|
12 | (1) |
|
|
13 | (1) |
|
|
14 | (4) |
|
A Computation Using Meissel's Formula |
|
|
18 | (2) |
|
A Computation Using Lehmer's Formula |
|
|
20 | (2) |
|
A Computer Program Using Lehmer's Formula |
|
|
22 | (1) |
|
|
23 | (1) |
|
|
24 | (2) |
|
|
26 | (4) |
|
|
30 | (2) |
|
Programming Mapes' Algorithm |
|
|
32 | (1) |
|
|
33 | (1) |
|
|
34 | (1) |
|
|
35 | (1) |
|
Comparison Between the Methods Discussed |
|
|
35 | (1) |
|
|
36 | (1) |
|
Chapter 2 The Primes Viewed at Large |
|
|
|
|
37 | (1) |
|
No Polynomial Can Produce Only Primes |
|
|
37 | (2) |
|
Formulas Yielding All Primes |
|
|
39 | (1) |
|
The Distribution of Primes Viewed at Large. Euclid's Theorem |
|
|
40 | (1) |
|
The Formulas of Gauss and Legendre for π(x). The Prime Number Theorem |
|
|
41 | (3) |
|
The Chebyshev Function θ(x) |
|
|
44 | (1) |
|
The Riemann Zeta-function |
|
|
44 | (3) |
|
The Zeros of the Zeta-function |
|
|
47 | (2) |
|
Conversion From f(x) Back to π(x) |
|
|
49 | (1) |
|
The Riemann Prime Number Formula |
|
|
50 | (2) |
|
|
52 | (1) |
|
The Influence of the Complex Zeros of ξ(i) on π(x) |
|
|
53 | (3) |
|
The Remainder Term in the Prime Number Theorem |
|
|
56 | (1) |
|
Effective Inequalities for π(x), pn, and θ(x) |
|
|
56 | (1) |
|
The Number of Primes in Arithmetic Progressions |
|
|
57 | (1) |
|
|
58 | (2) |
|
Chapter 3 Subtleties in the Distribution of Primes |
|
|
|
The Distribution of Primes in Short Intervals |
|
|
60 | (1) |
|
Twins and Some Other Constellations of Primes |
|
|
60 | (2) |
|
Admissible Constellations of Primes |
|
|
62 | (2) |
|
The Hardy-Littlewood Constants |
|
|
64 | (2) |
|
The Prime k-Tuples Conjecture |
|
|
66 | (1) |
|
Theoretical Evidence in Favour of the Prime k-Tuples Conjecture |
|
|
67 | (1) |
|
Numerical Evidence in Favour of the Prime k-Tuples Conjecture |
|
|
68 | (1) |
|
The Second Hardy-Littlewood Conjecture |
|
|
68 | (2) |
|
|
70 | (1) |
|
Modification of the Midpoint Sieve |
|
|
70 | (1) |
|
Construction of Superdense Admissible Constellations |
|
|
71 | (2) |
|
Some Dense Clusters of Primes |
|
|
73 | (1) |
|
The Distribution of Primes Between the Two Series 4n + 1 and 4n + 3 |
|
|
73 | (1) |
|
Graph of the Function π4,3(x)- π4,1(x) |
|
|
74 | (1) |
|
|
74 | (3) |
|
|
77 | (1) |
|
Large Gaps Between Consecutive Primes |
|
|
78 | (1) |
|
|
79 | (3) |
|
|
82 | (2) |
|
Chapter 4 The Recognition of Primes |
|
|
|
|
84 | (1) |
|
Tests of Primality and of Compositeness |
|
|
84 | (1) |
|
Factorization Methods as Tests of Compositeness |
|
|
85 | (1) |
|
Fermat's Theorem as Compositeness Test |
|
|
85 | (1) |
|
Fermat's Theorem as Primality Test |
|
|
85 | (1) |
|
Pseudoprimes and Probable Primes |
|
|
86 | (1) |
|
A Computer Program for Fermat's Test |
|
|
87 | (1) |
|
The Labor Involved in a Fermat Test |
|
|
88 | (1) |
|
|
89 | (1) |
|
|
90 | (1) |
|
Strong Pseudoprimes and a Primality Test |
|
|
91 | (2) |
|
A Computer Program for Strong Pseudoprime Tests |
|
|
93 | (1) |
|
Counts of Pseudoprimes and Carmichael Numbers |
|
|
94 | (1) |
|
Rigorous Primality Proofs |
|
|
95 | (1) |
|
Lehmer's Converse of Fermat's Theorem |
|
|
96 | (1) |
|
Formal Proof of Theorem 4.3 |
|
|
97 | (1) |
|
Ad Hoc Search for a Primitive Root |
|
|
98 | (1) |
|
|
99 | (1) |
|
Fermat Numbers and Pepin's Theorem |
|
|
100 | (2) |
|
Cofactors of Fermat Numbers |
|
|
102 | (1) |
|
Generalized Fermat Numbers |
|
|
102 | (1) |
|
A Relaxed Converse of Fermat's Theorem |
|
|
103 | (1) |
|
|
104 | (1) |
|
Tests of Compositeness for Numbers of the form N = h2n ± k |
|
|
105 | (1) |
|
|
105 | (1) |
|
Certificates of Primality |
|
|
106 | (1) |
|
Primality Tests of Lucasian Type |
|
|
107 | (1) |
|
|
107 | (1) |
|
|
108 | (1) |
|
|
108 | (3) |
|
|
111 | (1) |
|
Divisibility Properties of the Numbers Un |
|
|
112 | (3) |
|
Primality Proofs by Aid of Lucas Sequences |
|
|
115 | (2) |
|
Lucas Tests for Mersenne Numbers |
|
|
117 | (3) |
|
A Relaxation of Theorem 4.8 |
|
|
120 | (1) |
|
|
121 | (1) |
|
Lehmer-Pocklington's Theorem |
|
|
122 | (1) |
|
Pocklington-Type Theorems for Lucas Sequences |
|
|
123 | (1) |
|
Primality Tests for Integers of the form N = h 2n - 1, when 3|h |
|
|
124 | (1) |
|
Primality Tests for N = h 2n - 1, when 3|h |
|
|
125 | (4) |
|
The Combined N - 1 and N + 1 Test |
|
|
129 | (1) |
|
|
130 | (1) |
|
|
130 | (1) |
|
The Jacobi Sum Primality Test |
|
|
131 | (1) |
|
|
132 | (2) |
|
|
134 | (1) |
|
|
135 | (1) |
|
Running Time for the APRCL Test |
|
|
136 | (1) |
|
Elliptic Curve Primality Proving, ECPP |
|
|
136 | (1) |
|
The Goldwasser-Kilian Test |
|
|
137 | (1) |
|
|
138 | (1) |
|
|
139 | (2) |
|
Chapter 5 Classical Methods of Factorization |
|
|
|
|
141 | (1) |
|
When Do We Attempt Factorization? |
|
|
141 | (1) |
|
|
141 | (2) |
|
A Computer Implementation of Trial Division |
|
|
143 | (2) |
|
Euclid's Algorithm as an Aid to Factorization |
|
|
145 | (2) |
|
Fermat's Factoring Method |
|
|
147 | (2) |
|
|
149 | (2) |
|
|
151 | (1) |
|
|
152 | (3) |
|
Legendre's Factoring Method |
|
|
155 | (1) |
|
The Number of Prime Factors of Large Numbers |
|
|
156 | (1) |
|
How Does a Typical Factorization Look? |
|
|
157 | (1) |
|
|
158 | (1) |
|
The Distribution of Prime Factors of Various Sizes |
|
|
159 | (2) |
|
Dickman's Version of Theorem 5.4 |
|
|
161 | (1) |
|
|
161 | (1) |
|
The Size of the kth Largest Prime Factor of N |
|
|
162 | (2) |
|
|
164 | (1) |
|
Searching for Factors of Certain Forms |
|
|
165 | (1) |
|
Legendre's Theorem for the Factors of N = an ± bn |
|
|
165 | (4) |
|
Adaptation to Search for Factors of the Form p = 2kn + 1 |
|
|
169 | (1) |
|
Adaptation of Trial Division |
|
|
169 | (1) |
|
Adaptation of Fermat's Factoring Method |
|
|
170 | (1) |
|
Adaptation of Euclid's Algorithm as an Aid to Factorization |
|
|
171 | (1) |
|
|
171 | (2) |
|
Chapter 6 Modern Factorization Methods |
|
|
|
|
173 | (1) |
|
|
173 | (1) |
|
|
174 | (2) |
|
Phase 2 of the (p - 1)-Method |
|
|
176 | (1) |
|
|
177 | (1) |
|
|
177 | (3) |
|
A Computer Program for Pollard's rho Method |
|
|
180 | (2) |
|
An Algebraic Description of Pollard's rho Method |
|
|
182 | (1) |
|
Brent's Modification of Pollard's rho Method |
|
|
183 | (2) |
|
The Pollard-Brent Method for p = 2kn + 1 |
|
|
185 | (1) |
|
Shanks' Factoring Method SQUFOF |
|
|
186 | (4) |
|
A Computer Program for SQUFOF |
|
|
190 | (3) |
|
Comparison Between Pollard's rho Method and SQUFOF |
|
|
193 | (1) |
|
Morrison and Brillhart's Continued Fraction Method CFRAC |
|
|
193 | (1) |
|
|
194 | (2) |
|
An Example of a Factorization with CFRAC |
|
|
196 | (4) |
|
|
200 | (2) |
|
|
202 | (1) |
|
Results Achieved with CFRAC |
|
|
203 | (1) |
|
Running Time Analysis of CFRAC |
|
|
204 | (1) |
|
|
204 | (1) |
|
Smallest Solutions to Q(x) ≡ 0 mod p |
|
|
205 | (1) |
|
|
206 | (1) |
|
|
206 | (1) |
|
The Multiple Polynomial Quadratic Sieve, MPQS |
|
|
207 | (1) |
|
Results Achieved with MPQS |
|
|
207 | (1) |
|
Running Time Analysis of QS and MPQS |
|
|
208 | (1) |
|
The Schnorr-Lenstra Method |
|
|
209 | (1) |
|
Two Categories of Factorization Methods |
|
|
209 | (1) |
|
Lenstra's Elliptic Curve Method, ECM |
|
|
210 | (1) |
|
|
210 | (2) |
|
The Choice of A, B, and P1 |
|
|
212 | (1) |
|
|
212 | (2) |
|
Recent Results Achieved with ECM |
|
|
214 | (1) |
|
The Number Field Sieve, NFS |
|
|
214 | (1) |
|
Factoring Both in Z and in Z(z) |
|
|
215 | (1) |
|
|
215 | (1) |
|
The General Number Field Sieve, GNFS |
|
|
216 | (1) |
|
Running Times of NFS and GNFS |
|
|
217 | (1) |
|
Results Achieved with NFS. Factorization of F9 |
|
|
218 | (1) |
|
|
219 | (2) |
|
How Fast Can a Factorization Algorithm Be? |
|
|
221 | (3) |
|
|
224 | (2) |
|
Chapter 7 Prime Numbers and Cryptography |
|
|
|
|
226 | (1) |
|
|
226 | (2) |
|
|
228 | (1) |
|
|
228 | (1) |
|
How to Find the Recovery Exponent |
|
|
229 | (1) |
|
|
230 | (3) |
|
|
233 | (1) |
|
|
234 | (1) |
|
The Fixed Points of an RSA System |
|
|
235 | (1) |
|
How Safe is an RSA Cryptosystem? |
|
|
236 | (1) |
|
|
237 | (1) |
|
|
237 | (2) |
|
Appendix 1 Basic Concepts in Higher Algebra |
|
|
|
|
239 | (1) |
|
|
239 | (1) |
|
|
240 | (2) |
|
The Labor Involved in Euclid's Algorithm - |
|
|
242 | (1) |
|
A Definition Taken from the Theory of Algorithms |
|
|
242 | (1) |
|
A Computer Program for Euclid's Algorithm |
|
|
243 | (1) |
|
|
244 | (1) |
|
Binary Form of Euclid's Algorithm |
|
|
244 | (2) |
|
The Diophantine Equation ax + by = c |
|
|
246 | (1) |
|
|
246 | (2) |
|
Lagrange's Theorem. Cosets |
|
|
248 | (2) |
|
Abstract Groups. Isomorphic Groups |
|
|
250 | (21) |
|
The Direct Product of Two Given Groups |
|
|
251 | (1) |
|
|
252 | (1) |
|
|
252 | (1) |
|
|
253 | (2) |
|
|
255 | (2) |
|
Mappings. Isomorphisms and Homomorphisms |
|
|
257 | (1) |
|
|
258 | (1) |
|
The Conjugate or Inverse Character |
|
|
259 | (1) |
|
Homomorphisms and Group Characters |
|
|
260 | (1) |
|
|
260 | (1) |
|
Appendix 2 Bask Concepts in Higher Arithmetic |
|
|
|
Divisors. Common Divisors |
|
|
261 | (1) |
|
The Fundamental Theorem of Arithmetic |
|
|
261 | (1) |
|
|
262 | (2) |
|
|
264 | (1) |
|
Linear Congruences and Euclid's Algorithm |
|
|
265 | (1) |
|
Systems of Linear Congruences |
|
|
266 | (1) |
|
The Residue Classesmod p Constitute a Field |
|
|
267 | (1) |
|
The Primitive Residue Classesmod p |
|
|
268 | (2) |
|
The Structure of the Group Mn |
|
|
270 | (2) |
|
Homomorphisms of Mq when q is a Prime |
|
|
272 | (1) |
|
|
273 | (1) |
|
|
274 | (1) |
|
|
275 | (1) |
|
Appendix 3 Quadratic Residues |
|
|
|
|
276 | (1) |
|
Arithmetic Rules for Residues and Non-Residues |
|
|
276 | (2) |
|
Euler's Criterion for the Computation of (a / p) |
|
|
278 | (1) |
|
The Law of Quadratic Reciprocity |
|
|
279 | (2) |
|
|
281 | (2) |
|
A PASCAL Function for Computing (a / n) |
|
|
283 | (1) |
|
The Quadratic Congruence x2 ≡ c mod p |
|
|
284 | (1) |
|
|
284 | (1) |
|
|
285 | (1) |
|
Appendix 4 The Arithmetic of Quadratic Fields |
|
|
|
|
286 | (3) |
|
|
289 | (1) |
|
Associated Numbers in Q(√D) |
|
|
290 | (1) |
|
|
290 | (1) |
|
Fermat's Theorem in Q(√D) |
|
|
291 | (2) |
|
|
293 | (2) |
|
Factorization of Integers in Q(√D) |
|
|
295 | (1) |
|
|
296 | (1) |
|
Appendix 5 Higher Algebraic Number Fields |
|
|
|
|
297 | (1) |
|
|
297 | (1) |
|
Numbers in Q(z). The Ring Z(z) of Integers in Q(z) |
|
|
298 | (1) |
|
The Norm in Q(z). Units of Q(z) |
|
|
298 | (1) |
|
Divisibility and Primes in Z(z) |
|
|
299 | (1) |
|
The Field Q(3√-2) and the Ring Z(3√-2) |
|
|
299 | (1) |
|
|
300 | (3) |
|
|
303 | (1) |
|
Appendix 6 Algebraic Factors |
|
|
|
|
304 | (1) |
|
Factorization of Polynomials |
|
|
304 | (1) |
|
The Cyclotomic Polynomials |
|
|
305 | (3) |
|
|
308 | (1) |
|
|
308 | (1) |
|
Aurifeuillian Factorizations |
|
|
309 | (1) |
|
|
310 | (4) |
|
The Algebraic Structure of Aurifeuillian Numbers |
|
|
314 | (1) |
|
A formula by Gauss for xn - yn |
|
|
315 | (1) |
|
|
316 | (1) |
|
Appendix 7 Elliptic Curves |
|
|
|
|
317 | (2) |
|
Rational Points on Rational Cubics |
|
|
319 | (1) |
|
|
319 | (1) |
|
|
320 | (1) |
|
Rational Points on Elliptic Curves |
|
|
321 | (5) |
|
|
326 | (1) |
|
Appendix 8 Continued Fractions |
|
|
|
|
327 | (1) |
|
What Is a Continued Fraction? |
|
|
327 | (1) |
|
Regular Continued Fractions. Expansions |
|
|
328 | (1) |
|
Evaluating a Continued Fraction |
|
|
329 | (3) |
|
Continued Fractions as Approximations |
|
|
332 | (2) |
|
Euclid's Algorithm and Continued Fractions |
|
|
334 | (1) |
|
Linear Diophantine Equations and Continued Fractions |
|
|
334 | (1) |
|
|
335 | (2) |
|
Continued Fraction Expansions of Square Roots |
|
|
337 | (1) |
|
|
338 | (2) |
|
The Maximal Period-Length |
|
|
340 | (1) |
|
|
341 | (1) |
|
Continued Fractions and Quadratic Residues |
|
|
341 | (1) |
|
|
342 | (1) |
|
Appendix 9 Multiple-Precision Arithmetic |
|
|
|
|
343 | (1) |
|
Various Objectives for a Multiple-Precision Package |
|
|
343 | (1) |
|
How to Store Multi-Precise Integers |
|
|
344 | (1) |
|
Addition and Subtraction of Multi-Precise Integers |
|
|
345 | (1) |
|
Reduction in Length of Multi-Precise Integers |
|
|
346 | (1) |
|
Multiplication of Multi-Precise Integers |
|
|
346 | (2) |
|
Division of Multi-Precise Integers |
|
|
348 | (1) |
|
Input and Output of Multi-Precise Integers |
|
|
349 | (1) |
|
A Complete Package for Multiple-Precision Arithmetic |
|
|
349 | (6) |
|
A Computer Program for Pollard's rho Method |
|
|
355 | (2) |
|
Appendix 10 Fast Multiplication of Large Integers |
|
|
|
The Ordinary Multiplication Algorithm |
|
|
357 | (1) |
|
Double Length Multiplication |
|
|
358 | (2) |
|
Recursive Use of Double Length Multiplication Formula |
|
|
360 | (1) |
|
A Recursive Procedure for Squaring Large Integers |
|
|
361 | (3) |
|
Fractal Structure of Recursive Squaring |
|
|
364 | (1) |
|
|
364 | (1) |
|
|
364 | (1) |
|
Appendix 11 The Stieltjes Integral |
|
|
|
|
365 | (1) |
|
Functions With Jump Discontinuities |
|
|
365 | (1) |
|
|
366 | (1) |
|
Definition of the Stieltjes Integral |
|
|
367 | (2) |
|
Rules of Integration for Stieltjes Integrals |
|
|
369 | (1) |
|
Integration by Parts of Stieltjes Integrals |
|
|
370 | (1) |
|
|
371 | (1) |
|
|
372 | (2) |
Tables. For Contents |
|
374 | (83) |
List of Textbooks |
|
457 | (1) |
Index |
|
458 | |