American Scientist

Prime Numbers: A Computational Perspective. Richard Crandall and Carl Pomerance. xvi + 545 pp. Springer-Verlag, 2001. $49.95

Although everyone knows what a prime number is, the implications of this simple concept are amazingly deep and diverse. As Richard Crandall and Carl Pomerance note in Prime Numbers, "The basic notion of primality can be accessible to a child, yet no human mind harbors anything like a complete picture."

The advent of accessible and fast methods of computation has had a profound impact on how we view prime numbers, and this book summarizes the state of the art regarding algorithms for dealing with primes. The two central algorithmic problems in this area are the determination of primality for a given integer and the factoring of an integer into prime factors. The book covers these and lots more, touching on many important computational approaches to problems of number theory.

One aspect of prime numbers that has intrigued both professionals and amateurs is the lore that has built up around special primes: Numerologists have enjoyed the connection with perfect numbers, and the determination of Fermat primes (primes of the form 2²ⁿ+1) has inspired some of the largest computations in history. In a playful chapter on "The Ubiquity of Prime Numbers," the authors mention several scientific investigations in which primes have played a role—for example, a famous one concerning the 13- and 17-year life cycles of a type of cicada.

Perhaps the most famous application of prime numbers to general culture came in the mid-1970s, when primes were shown to be the basis of a radically new and presumably secure type of encryption, now known as the RSA method. This encryption system relies on the fast generation of large prime numbers (and the extreme slowness of algorithms to break a number into its prime factors): The fact that factoring is, most likely, computationally hard is what makes the cryptosystem secure. But even before this development, number theory had played an important role in diverse areas of science. Prime Numbers covers some of these applications in depth, such as the use of primes in the generation of random numbers and in the evaluation of multidimensional integrals. One of my favorite applications of number theory has to do with the Madelung constant for salt (the energy holding a sodium ion in place in a sodium chloride lattice); anyone interested in that topic at the crossroads of chemistry and solid-state physics should consult Crandall's papers on the subject. Although number theory is indeed a beautiful subject with deep historical roots, the fact that it is used in serious ways in modern science and computer science adds greatly to its appeal.

The bulk of the book focuses closely on the mathematics of the primes from an algorithmic standpoint, and the reader will have to be well versed in elementary number theory to get into this material. For such a reader, the depth of the book is superb. For example, a noteworthy 20th-century development concerns certification of primes. It turns out that for any prime number, there is a short proof of primality of that number, where "short" means that the length of the proof is a polynomial function of the number of digits of the prime (as opposed to the prime number itself; this is a critical distinction in computational complexity). Pomerance is an expert in this area, and the book contains a very detailed discussion of the known methods of finding such short proofs.

The exercises are a gold mine of interesting examples, pointers to the literature and potential research projects. For example, chapter 3, "Recognizing Primes and Composites," contains 40 exercises and 9 research problems.

Prime Numbers is a welcome addition to the literature of number theory—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.—Stan Wagon, Mathematics, Macalester College, St. Paul, Minnesota