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 |
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 โ 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 โgrammar-schoolโ 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