Prime Numbers

by Crandall, Richard; Pomerance, Carl

• ISBN13: 9780387947778
• ISBN10: 0387947779
• Format: Hardcover
• Copyright: 2001-04-01
• Publisher: Telos Pr

Summary

Prime numbers beckon to the beginner, as the basic notion of primality is accessible even to a child. Yet, some of the simplest questions about primes have confounded humankind for millennia. In the new edition of this highly successful book, Richard Crandall and Carl Pomerance have provided updated material on theoretical, computational, and algorithmic fronts. New results discussed include the AKS test for recognizing primes, computational evidence for the Riemann hypothesis, a fast binary algorithm for the greatest common divisor, nonuniform fast Fourier transforms, and more. The authors also list new computational records and survey new developments in the theory of prime numbers, including the magnificent proof that there are arbitrarily long arithmetic progressions of primes, and the final resolution of the Catalan problem. Numerous exercises have been added. Book jacket.

Author Biography

Carl Pomerance is the recipient of the Chauvenet and Conant Prizes for expository mathematical writing. He is currently a mathematics professor at Dartmouth College, having previously been at the University of Georgia and Bell Labs

Table of Contents

Preface	vii
Primes!	1	(76)
Problems and progress	1	(11)
Fundamental theorem and fundamental problem	1	(1)
Technological and algorithmic progress	2	(3)
The infinitude of primes	5	(2)
Asymptotic relations and order nomenclature	7	(2)
How primes are distributed	9	(3)
Celebrated conjectures and curiosities	12	(7)
Twin primes	12	(3)
Prime k-tuples and hypothesis H	15	(1)
The Goldbach conjecture	16	(2)
The convexity question	18	(1)
Prime-producing formulae	18	(1)
Primes of special form	19	(11)
Mersenne primes	20	(4)
Fermat numbers	24	(4)
Certain presumably rare primes	28	(2)
Analytic number theory	30	(15)
The Riemann zeta function	30	(5)
Computational successes	35	(1)
Dirichlet L-functions	36	(4)
Exponential sums	40	(4)
Smooth numbers	44	(1)
Exercises	45	(24)
Research problems	69	(8)
Number-Theoretical Tools	77	(32)
Modular arithmetic	77	(6)
Greatest common divisor and inverse	77	(2)
Powers	79	(2)
Chinese remainder theorem	81	(2)
Polynomial arithmetic	83	(6)
Greatest common divisor for polynomials	83	(2)
Finite fields	85	(4)
Squares and roots	89	(12)
Quadratic residues	89	(4)
Square roots	93	(3)
Finding polynomial roots	96	(3)
Representation by quadratic forms	99	(2)
Exercises	101	(5)
Research problems	106	(3)
Recognizing Primes And Composites	109	(50)
Trial division	109	(4)
Divisibility tests	109	(1)
Trial division	110	(1)
Practical considerations	111	(1)
Theoretical considerations	112	(1)
Sieving	113	(6)
Sieving to recognize primes	113	(1)
Eratosthenes pseudocode	114	(1)
Sieving to construct a factor table	114	(1)
Sieving to construct complete factorizations	115	(1)
Sieving to recognize smooth numbers	115	(1)
Sieving a polynomial	116	(2)
Theoretical considerations	118	(1)
Pseudoprimes	119	(4)
Fermat pseudoprimes	120	(1)
Carmichael numbers	121	(2)
Probable primes and witnesses	123	(7)
The least witness for n	128	(2)
Lucas pseudoprimes	130	(10)
Fibonacci and Lucas pseudoprimes	131	(2)
Grantham's Frobenius test	133	(1)
Implementing the Lucas and quadratic Frobenius tests	134	(3)
Theoretical considerations and stronger tests	137	(2)
The general Frobenius test	139	(1)
Counting primes	140	(10)
Combinatorial method	141	(5)
Analytic method	146	(4)
Exercises	150	(6)
Research problems	156	(3)
Primality Proving	159	(32)
The n - 1 test	159	(8)
The Lucas theorem and Pepin test	159	(1)
Partial factorization	160	(4)
Succinct certificates	164	(3)
The n + 1 test	167	(8)
The Lucas-Lehmer test	167	(3)
An improved n + 1 test, and a combined n2 - 1 test	170	(2)
Divisors in residue classes	172	(3)
The finite field primality test	175	(5)
Gauss and Jacobi sums	180	(5)
Gauss sums test	180	(5)
Jacobi sums test	185	(1)
Exercises	185	(4)
Research problems	189	(2)
Exponential Factoring Algorithms	191	(34)
Squares	191	(4)
Fermat method	191	(2)
Lehman method	193	(1)
Factor sieves	194	(1)
Monte Carlo methods	195	(5)
Pollard rho method for factoring	195	(2)
Pollard rho method for discrete logarithms	197	(2)
Pollard lambda method for discrete logarithms	199	(1)
Baby-steps, giant-steps	200	(2)
Pollard p - 1 method	202	(2)
Polynomial evaluation method	204	(1)
Binary quadratic forms	204	(12)
Quadratic form fundamentals	204	(3)
Factoring with quadratic form representations	207	(3)
Composition and the class group	210	(3)
Ambiguous forms and factorization	213	(3)
Exercises	216	(4)
Research problems	220	(5)
Subexponential Factoring Algorithms	225	(58)
The quadratic sieve factorization method	225	(17)
Basic QS	225	(5)
Basic QS: A summary	230	(2)
Fast matrix methods	232	(2)
Large prime variations	234	(3)
Multiple polynomials	237	(1)
Self initialization	238	(2)
Zhang's special quadratic sieve	240	(2)
Number field sieve	242	(23)
Basic NFS: Strategy	243	(1)
Basic NFS: Exponent vectors	244	(5)
Basic NFS: Complexity	249	(3)
Basic NFS: Obstructions	252	(3)
Basic NFS: Square roots	255	(1)
Basic NFS: Summary algorithm	256	(2)
NFS: Further considerations	258	(7)
Rigorous factoring	265	(1)
Index-calculus method for discrete logarithms	266	(4)
Discrete logarithms in prime finite fields	267	(2)
Discrete logarithms via smooth polynomials and smooth algebraic integers	269	(1)
Exercises	270	(9)
Research problems	279	(4)
Elliptic Curve Arithmetic	283	(68)
Elliptic curve fundamentals	283	(4)
Elliptic arithmetic	287	(10)
The theorems of Hasse, Deuring, and Lenstra	297	(2)
Elliptic curve method	299	(12)
Basic ECM algorithm	300	(3)
Optimization of ECM	303	(8)
Counting points on elliptic curves	311	(21)
Shanks-Mestre method	311	(4)
Schoof method	315	(6)
Atkin-Morain method	321	(11)
Elliptic curve primality proving (ECPP)	332	(6)
Goldwasser-Kilian primality test	332	(4)
Atkin-Morain primality test	336	(2)
Exercises	338	(6)
Research problems	344	(7)
The Ubiquity Of Prime Numbers	351	(54)
Cryptography	351	(10)
Diffie-Hellman key exchange	351	(2)
RSA cryptosystem	353	(2)
Elliptic curve cryptosystems (ECCs)	355	(5)
Coin-flip protocol	360	(1)
Random-number generation	361	(7)
Modular methods	361	(7)
Quasi-Monte Carlo (qMC) methods	368	(11)
Discrepancy theory	368	(3)
Specific qMC sequences	371	(2)
Primes on Wall Street?	373	(6)
Diophantine analysis	379	(3)
Quantum computation	382	(6)
Intuition on quantum Turing machines (QTMs)	383	(3)
The Shor quantum algorithm for factoring	386	(2)
Curious, anecdotal, and interdisciplinary references to primes	388	(6)
Exercises	394	(4)
Research problems	398	(7)
Fast Algorithms For Large-Integer Arithmetic	405	(96)
Tour of ``grammar-school'' methods	405	(4)
Multiplication	405	(1)
Squaring	406	(1)
Div and mod	407	(2)
Enhancements to modular arithmetic	409	(10)
Montgomery method	409	(3)
Newton methods	412	(4)
Moduli of special form	416	(3)
Exponentiation	419	(6)
Basic binary ladders	420	(2)
Enhancements to ladders	422	(3)
Enhancements for god and inverse	425	(6)
Binary god algorithms	425	(2)
Special inversion algorithms	427	(1)
Recursive god for very large operands	428	(3)
Large-integer multiplication	431	(34)
Karatsuba and Toom-Cook methods	431	(3)
Fourier transform algorithms	434	(9)
Convolution theory	443	(5)
Discrete weighted transform (DWT) methods	448	(6)
Number-theoretical transform methods	454	(3)
Schonhage method	457	(2)
Nussbaumer method	459	(3)
Complexity of multiplication algorithms	462	(1)
Application to the Chinese remainder theorem	463	(2)
Polynomial arithmetic	465	(8)
Polynomial multiplication	465	(1)
Fast polynomial inversion and remaindering	466	(3)
Polynomial evaluation	469	(4)
Exercises	473	(16)
Research problems	489	(12)
Book Pseudocode	495	(6)
References	501	(26)
Index	527