Prime Numbers

by Crandall, Richard; Pomerance, Carl

• ISBN13: 9780387252827
• ISBN10: 0387252827
• Edition: 2nd
• Format: Hardcover
• Copyright: 2005-10-01
• Publisher: Springer Nature

Summary

Prime numbers beckon to the beginner, the basic notion of primality being accessible to a child. Yet, some of the simplest questions about primes have stumped humankind for millennia. In this book, the authors concentrate on the computational aspects of prime numbers, such as recognizing primes and discovering the fundamental prime factors of a given number. Over 100 explicit algorithms cast in detailed pseudocode are included in the book. Applications and theoretical digressions serve to illuminate, justify, and underscore the practical power of these algorithms. The 2 nd edition adds new material on primality and algorithms and updates all the numerical records, such as the largest prime, etc. It has been revised throughout. From the reviews of the first edition: "a? The exercises are a gold mine of interesting examples, pointers to the literature and potential research projects. a? Prime Numbers is a welcome addition to the literature of number theorya??comprehensive, up-to-date and written with style. It will be useful to anyone interested in algorithms dealing with the arithmetic of the integers and related computational issues." American Scientist "Destined to become a definitive textbook conveying the most modern computational ideas about prime numbers and factoring, this book will stand as an excellent reference for this kind of computation, and thus be of interest to both educators and researchers. It is also a timely book, since primes and factoring have reached a certain vogue, partly because of cryptography. a? " La??Enseignement Math??matique "The book is an excellent resource for anyone who wants to understand these algorithms, learn how to implement them, and make them go fast. It's also a lot of fun to read! It's rare to say this of a math book, but open Prime Numbers to a random page and it's hard to put down. Crandall and Pomerance have written a terrific book." Bulletin of the AMS

Author Biography

Richard Crandall currently holds the title of Apple Distinguished Scientist, having previously been Apples Chief Cryptographer, the Chief Scientist at NeXT, Inc., and recipient of the Vollum Chair of Science at Reed College. His primary interest is interdisciplinary scientific computation, though he has authored numerous theoretical papers in quantum physics, biology, mathematics, and chemistry, as well as various patents across engineering fields. Carl Pomerance received his Ph.D. in mathematics from Harvard University in 1972. Currently he is a professor at Dartmouth College. A popular lecturer and winner of the Chauvenet and Conant Prizes for expository mathematical writing, Pomerance is well known for his research in computational number theory, his efforts having produced important algorithms now in wide use.

Table of Contents

Preface	vii
Primes!	1	(82)
Problems and progress	1	(13)
Fundamental theorem and fundamental problem	1	(1)
Technological and algorithmic progress	2	(4)
The infinitude of primes	6	(2)
Asymptotic relations and order nomenclature	8	(2)
How primes are distributed	10	(4)
Celebrated conjectures and curiosities	14	(8)
Twin primes	14	(3)
Prime k-tuples and hypothesis H	17	(1)
The Goldbach conjecture	18	(2)
The convexity question	20	(1)
Prime-producing formulae	21	(1)
Primes of special form	22	(11)
Mersenne primes	22	(5)
Fermat numbers	27	(4)
Certain presumably rare primes	31	(2)
Analytic number theory	33	(16)
The Riemann zeta function	33	(5)
Computational successes	38	(1)
Dirichlet L-functions	39	(4)
Exponential sums	43	(5)
Smooth numbers	48	(1)
Exercises	49	(26)
Research problems	75	(8)
Number-Theoretical Tools	83	(34)
Modular arithmetic	83	(6)
Greatest common divisor and inverse	83	(2)
Powers	85	(2)
Chinese remainder theorem	87	(2)
Polynomial arithmetic	89	(7)
Greatest common divisor for polynomials	89	(2)
Finite fields	91	(5)
Squares and roots	96	(12)
Quadratic residues	96	(3)
Square roots	99	(4)
Finding polynomial roots	103	(3)
Representation by quadratic forms	106	(2)
Exercises	108	(5)
Research problems	113	(4)
Recognizing Primes and Composites	117	(56)
Trial division	117	(4)
Divisibility tests	117	(1)
Trial division	118	(1)
Practical considerations	119	(1)
Theoretical considerations	120	(1)
Sieving	121	(7)
Sieving to recognize primes	121	(1)
Eratosthenes pseudocode	122	(1)
Sieving to construct a factor table	122	(1)
Sieving to construct complete factorizations	123	(1)
Sieving to recognize smooth numbers	123	(1)
Sieving a polynomial	124	(2)
Theoretical considerations	126	(2)
Recognizing smooth numbers	128	(3)
Pseudoprimes	131	(4)
Fermat pseudoprimes	131	(2)
Carmichael numbers	133	(2)
Probable primes and witnesses	135	(7)
The least witness for n	140	(2)
Lucas pseudoprimes	142	(10)
Fibonacci and Lucas pseudoprimes	142	(3)
Grantham's Frobenius test	145	(1)
Implementing the Lucas and quadratic Frobenius tests	146	(3)
Theoretical considerations and stronger tests	149	(2)
The general Frobenius test	151	(1)
Counting primes	152	(10)
Combinatorial method	152	(6)
Analytic method	158	(4)
Exercises	162	(6)
Research problems	168	(5)
Primality Proving	173	(52)
The n - 1 test	173	(8)
The Lucas theorem and Pepin test	173	(1)
Partial factorization	174	(5)
Succinct certificates	179	(2)
The n + 1 test	181	(9)
The Lucas--Lehmer test	181	(3)
An improved n + 1 test, and a combined n2 - 1 test	184	(2)
Divisors in residue classes	186	(4)
The finite field primality test	190	(4)
Gauss and Jacobi sums	194	(6)
Gauss sums test	194	(5)
Jacobi sums test	199	(1)
The primality test of Agrawal, Kayal, and Saxena (AKS test)	200	(17)
Primality testing with roots of unity	201	(4)
The complexity of Algorithm 4.5.1	205	(2)
Primality testing with Gaussian periods	207	(6)
A quartic time primality test	213	(4)
Exercises	217	(5)
Research problems	222	(3)
Exponential Factoring Algorithms	225	(36)
Squares	225	(4)
Fermat method	225	(2)
Lehman method	227	(1)
Factor sieves	228	(1)
Monte Carlo methods	229	(6)
Pollard rho method for factoring	229	(3)
Pollard rho method for discrete logarithms	232	(1)
Pollard lambda method for discrete logarithms	233	(2)
Baby-steps, giant-steps	235	(1)
Pollard p - 1 method	236	(2)
Polynomial evaluation method	238	(1)
Binary quadratic forms	239	(12)
Quadratic form fundamentals	239	(3)
Factoring with quadratic form representations	242	(3)
Composition and the class group	245	(3)
Ambiguous forms and factorization	248	(3)
Exercises	251	(4)
Research problems	255	(6)
Subexponential Factoring Algorithms	261	(58)
The quadratic sieve factorization method	261	(17)
Basic QS	261	(5)
Basic QS: A summary	266	(2)
Fast matrix methods	268	(2)
Large prime variations	270	(3)
Multiple polynomials	273	(1)
Self initialization	274	(2)
Zhang's special quadratic sieve	276	(2)
Number field sieve	278	(23)
Basic NFS: Strategy	279	(1)
Basic NFS: Exponent vectors	280	(5)
Basic NFS: Complexity	285	(3)
Basic NFS: Obstructions	288	(3)
Basic NFS: Square roots	291	(1)
Basic NFS: Summary algorithm	292	(2)
NFS: Further considerations	294	(7)
Rigorous factoring	301	(1)
Index-calculus method for discrete logarithms	302	(4)
Discrete logarithms in prime finite fields	303	(2)
Discrete logarithms via smooth polynomials and smooth algebraic integers	305	(1)
Exercises	306	(9)
Research problems	315	(4)
Elliptic Curve Arithmetic	319	(68)
Elliptic curve fundamentals	319	(4)
Elliptic arithmetic	323	(10)
The theorems of Hasse, Deuring, and Lenstra	333	(2)
Elliptic curve method	335	(12)
Basic ECM algorithm	336	(3)
Optimization of ECM	339	(8)
Counting points on elliptic curves	347	(21)
Shanks--Mestre method	347	(4)
Schoof method	351	(7)
Atkin--Morain method	358	(10)
Elliptic curve primality proving (ECPP)	368	(6)
Goldwasser--Kilian primality test	368	(3)
Atkin--Morain primality test	371	(2)
Fast primality-proving via ellpitic curves (fast ECPP)	373	(1)
Exercises	374	(6)
Research problems	380	(7)
The Ubiquity of Prime Numbers	387	(56)
Cryptography	387	(10)
Diffie--Hellman key exchange	387	(2)
RSA cryptosystem	389	(2)
Elliptic curve cryptosystems (ECCs)	391	(5)
Coin-flip protocol	396	(1)
Random-number generation	397	(7)
Modular methods	398	(6)
Quasi-Monte Carlo (qMC) methods	404	(11)
Discrepancy theory	404	(3)
Specific qMC sequences	407	(2)
Primes on Wall Street?	409	(6)
Diophantine analysis	415	(3)
Quantum computation	418	(6)
Intuition on quantum Turing machines (QTMs)	419	(3)
The Shor quantum algorithm for factoring	422	(2)
Curious, anecdotal, and interdisciplinary references to primes	424	(7)
Exercises	431	(5)
Research problems	436	(7)
Fast Algorithms for Large-Integer Arithmetic	443	(98)
Tour of ``grammar-school'' methods	443	(4)
Multiplication	443	(1)
Squaring	444	(1)
Div and mod	445	(2)
Enhancements to modular arithmetic	447	(10)
Montgomery method	447	(3)
Newton methods	450	(4)
Moduli of special form	454	(3)
Exponentiation	457	(6)
Basic binary ladders	458	(2)
Enhancements to ladders	460	(3)
Enhancements for gcd and inverse	463	(10)
Binary gcd algorithms	463	(2)
Special inversion algorithms	465	(1)
Recursive-gcd schemes for very large operands	466	(7)
Large-integer multiplication	473	(36)
Karatsuba and Toom--Cook methods	473	(3)
Fourier transform algorithms	476	(12)
Convolution theory	488	(5)
Discrete weighted transform (DWT) methods	493	(5)
Number-theoretical transform methods	498	(4)
Schonhage method	502	(1)
Nussbaumer method	503	(3)
Complexity of multiplication algorithms	506	(2)
Application to the Chinese remainder theorem	508	(1)
Polynomial arithmetic	509	(9)
Polynomial multiplication	510	(1)
Fast polynomial inversion and remaindering	511	(3)
Polynomial evaluation	514	(4)
Exercises	518	(17)
Research problems	535	(6)
Appendix: Book Pseudocode	541	(6)
References	547	(30)
Index	577