Prime numbers : computational perspective

Includes bibliography (p. 547-575) and references.

1 Primes!
2 Number-Theoretical Tools
3 Recognizing Primes and Composites.
4 Primality Proving
5 Exponential Factoring Algorithms
6 Subexponential Factoring Algorithms
7 Elliptic Curve Arithmetic
8 The Ubiquity of Prime Numbers
9 Fast Algorithms for Large-Integer Arithmetic

Prime numbers beckon to the beginner, as the basic notion of primality is accessible even to children. 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. Richard Crandall currently holds the title of Apple Distinguished Scientist, having previously been Apple's Chief Cryptographer, the Chief Scientist at NeXT, Inc., and recipient of the Vollum Chair of Science at Reed College.