Author	Crandall, Richard. author
Title	Prime Numbers [electronic resource] : A Computational Perspective / by Richard Crandall, Carl Pomerance
Imprint	New York, NY : Springer New York, 2001
Connect to	http://dx.doi.org/10.1007/978-1-4684-9316-0
Descript	XV, 547p. online resource

In this volume we have endeavored to provide a middle ground-hopefully even a bridge-between "theory" and "experiment" in the matter of prime numbers. Of course, we speak of number theory and computer experiment. There are great books on the abstract properties of prime numbers. Each of us working in the field enjoys his or her favorite classics. But the experimental side is relatively new. Even though it can be forcefully put that computer science is by no means young, as there have arguably been four or five computer "revolutions" by now, it is the case that the theoretical underpinnings of prime numbers go back centuries, even millennia. So, we believe that there is room for treatises based on the celebrated classical ideas, yet authored from a modern computational perspective. Design and scope of this book The book combines the essentially complementary areas of expertise of the two authors. (One author (RC) is more the computationalist, the other (CP) more the theorist. ) The opening chapters are in a theoretical vein, even though some explicit algorithms are laid out therein, while heavier algorithmic concentration is evident as the reader moves well into the book. Whether in theoretical or computational writing mode, we have tried to provide the most up-to-date aspects of prime-number study. What we do not do is sound the very bottom of every aspect

1 Primes! -- 1.1 Problems and progress -- 1.2 Celebrated conjectures and curiosities -- 1.3 Primes of special form -- 1.4 Analytic number theory -- 1.5 Exercises -- 1.6 Research problems -- 2 Number-Theoretical Tools -- 2.1 Modular arithmetic -- 2.2 Polynomial arithmetic -- 2.3 Squares and roots -- 2.4 Exercises -- 2.5 Research problems -- 3. Recognizing Primes and Composites -- 3.1 Trial division -- 3.2 Sieving -- 3.3 Pseudoprimes -- 3.4 Probable primes and witnesses -- 3.5 Lucas pseudoprimes -- 3.6 Counting primes -- 3.7 Exercises -- 3.8 Research problems -- 4. Primality Proving -- 4.1 The n - 1 test -- 4.2 The n + 1 test -- 4.3 The finite field primality test -- 4.4 Gauss and Jacobi sums -- 4.5 Exercises -- 4.6 Research problems -- 5 Exponential Factoring Algorithms -- 5.1 Squares -- 5.2 Monte Carlo methods -- 5.3 Baby-steps, giant-steps -- 5.4 Pollard p โ{128}{148} 1 method -- 5.5 Polynomial evaluation method -- 5.6 Binary quadratic forms -- 5.7 Exercises -- 5.8 Research problems -- 6 Subexponential Factoring Algorithms -- 6.1 The quadratic sieve factorization method -- 6.2 Number field sieve -- 6.3 Rigorous factoring -- 6.4 Index-calculus method for discrete logarithms -- 6.5 Exercises -- 6.6 Research problems -- 7. Elliptic Curve Arithmetic -- 7.1 Elliptic curve fundamentals -- 7.2 Elliptic arithmetic -- 7.3 The theorems of Hasse, Deuring, and Lenstra -- 7.4 Elliptic curve method -- 7.5 Counting points on elliptic curves -- 7.6 Elliptic curve primality proving (ECPP) -- 7.7 Exercises -- 7.8 Research problems -- 8. The Ubiquity of Prime Numbers -- 8.1 Cryptography -- 8.2 Random-number generation -- 8.3 Quasi-Monte Carlo (qMC) methods -- 8.4 Diophantine analysis -- 8.5 Quantum computation -- 8.6 Curious, anecdotal, and interdisciplinary references to primes -- 8.7 Exercises -- 8.8 Research problems -- 9 Fast Algorithms for Large-Integer Arithmetic -- 9.1 Tour of โ{128}{156}grammar-schoolโ{128}{157} methods -- 9.2 Enhancements to modular arithmetic -- 9.3 Exponentiation -- 9.4 Enhancements for gcd and inverse -- 9.5 Large-integer multiplication -- 9.6 Polynomial arithmetic -- 9.7 Exercises -- 9.8 Research problems -- Book Pseudocode -- References