MAA Reviews

<< homepage

 

show printer friendly

send to a friend

Prime Numbers: A Computational Perspective

See the table of contents

This book is in the MAA's basic library list.

MAA Review

Prime numbers hold a fascination for almost everyone who thinks about numbers, amateur or professional, student or teacher. The questions one can ask are so simple. Sometimes, the answers come from equally simple insights. Often, the answers require the full complexity of research at the very frontiers of mathematics. Even the seemingly simple operations of factorization and prime recognition are now undertaken with algorithms developed from the study of elliptic curves and of number fields. And yet, one of the most important recent breakthroughs in primality testing, the polynomial time algorithm of Agarwal, Kayal and Saxena (AKS), announced in 2002, draws on nothing beyond standard undergraduate abstract algebra. In fact, Kayal and Saxena were undergraduates when they and Agarwal developed the algorithm.

We are indebted to Crandall and Pomerance for producing this second edition only five years after the first edition appeared. A lot has happened in those five years. The largest known prime now has over 7.8 million digits, 2^25964951 ­– 1, discovered in February, 2005 by Nowak, Woltman, and Kurowski. The Special Number Field Sieve was used by Aoki, Kida, Shimoyama, Sonoda, and Ueda in 2004 to factor the 248-digit behemoth, 2⁸²¹ + 2⁴¹¹ + 1. But the real progress has been in the theoretical advances and the use of that theory to develop practical algorithms. Crandall and Pomerance are perfectly paired to explain both sides of these advances, Carl Pomerance for the theoretical underpinnings and Richard Crandall for the algorithmic implementation. Actually, the term algorithmic implementation suggests less than is actually involved. How does one multiply two 7 million-digit integers efficiently? Breakthroughs since the first edition now make it possible for a desktop PC to multiply two billion-digit integers in about a minute. The real speed-up has come not from faster processing times but from the application of Discrete Fourier Transforms to the problem of multiplication.

The past five years have seen proofs of two long-standing conjectures about primes. One of these is the proof of Catalan’s conjecture, published by P. Mihailescu in 2004. This says that 3² and 2³ is the only pair of integer powers (with exponents > 1) that differ by exactly 1. The other, announced in 2004, is the proof by B. Green and T. Tao that the primes contain arbitrarily long arithmetic sequences. This second result is particularly notable because it uses tools from harmonic analysis.

Much more has happened to improve the algorithms. F. Morain has developed a new version of Elliptic Curve Primality Proving, fastECPP. Using it, he, Franke, Kleinjung, and Wirth proved that 4405²⁶³⁸ + 2638⁴⁴⁰⁵, an integer of over 15,000 digits, is prime. D. Bernstein has invented an efficient algorithm for identifying integers with small prime factors when sieve methods are not appropriate. D. Stehlé and P. Zimmermann have an improved algorithm for finding gcd’s. The new edition also surveys progress in counting points on elliptic curves, on the Fast Fourier Transform (FFT) which can now handle a billion complex input elements, and on nonuniform FFT.

This is more than a book with a lot of information. The information is presented at multiple levels so that it is useful. If you simply want a survey of what has been done and what can be computed, you will find that here. If you want some understanding of what is involved in Elliptic Curve Primality Proving, ECPP, or the Generalized Number Field Sieve, GNFS, you can easily pick this information from the relevant chapter or section without getting bogged down in subject-specific terminology or details that are irrelevant to the big picture. If you want to try your own implementation of one of the algorithms, easily interpretable pseudo-code is provided. If you want to know why an algorithm works or broadly why a certain result is true, you will find clear explanations that do not assume any more than a well-educated undergraduate mathematics major should know. If you want to go into the details of the deeper proofs, that you will not find, but you will get full references.

For anyone with an interest in primes and at least a solid undergraduate education in mathematics, this is a book that you must have. If you bought the first edition but really want to stay current, then it is worth investing in the second. Our knowledge of prime numbers is advancing fast enough that there are substantial differences between these volumes. I hope that Crandall and Pomerance are already looking toward the third edition for 2010.

David M. Bressoud is DeWitt Wallace Professor Mathematics at Macalester College in St. Paul, Minnesota.

BLL* — The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

Comments

Submit your Review