zbMATH — the first resource for mathematics

Prime numbers. A computational perspective. 2nd ed. (English) Zbl 1088.11001
New York, NY: Springer (ISBN 0-387-25282-7/hbk). xv, 597 p. ; (2005).
This is an absolutely wonderful book! Written in a readable and enthusiastic style the authors try to share the elegance of the prime numbers with the readers, thereby also unravelling some of the complexity and power hidden within such numbers. Weaving together a wealth of ideas and experience from theory and practice they enable the reader to have more than a glimpse into the current state of knowledge as well as the likely prospects for the immediate future.
The titles for the chapters are: 1. Primes, 2. Number-Theoretic 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. Each chapter ends with a good collection of exercises set out in a well-organised manner. Many of these are research projects with suitable pointers, directions and useful suggestions. As part of the title of the book already indicates, the computational aspect takes on a prominent role. The driving force in the development in this area is, of course, the advent of powerful computing machines, followed by the construction of efficient algorithms, many of which making spectacular breakthoughs for some basic problems. There are countless algorithms accompanying the text; these are given in pseudocode – a fusion of English and C languages – together with plenty of helpful comments within the codes. The algorithms not only serve to illuminate and justify the methods used, they also underscore the practical power of a constructive argument.
Almost any chapter or section can be singled out for high praise. Since the subjects of factorisation and the computation of discrete logarithms are now part of a vast research field, indeed even an industry, there is much to be learned for both the theoretician and the practitioner from the text. Thus the authors gave authorative background and much of the idea and excitement behind the development of the quadratic sieve, the number field sieve and the elliptic curve method. Some of the development highlights the interplay between theoretical complexity estimates and good programming intuitions; indeed it is clear that such recent rapid progress with these problems would not have taken place without this interplay. Such ideas and methods also give some urgency to the study of particular topics, one such being the distribution of smooth numbers.
This second edition (see Zbl 0995.11072 for a review of the first ed.) is thoroughly revised, with up-dated listing of computational records and interesting new results – one such being an exposition of the AKS test for recognising primes. The book is written so that newcomers to the subject will not find it daunting, and yet it has already acquired the status of a standard reference for research workers. Indeed it is destined to become a definitive text on the computational aspect of prime numbers and factoring.

11-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to number theory
68W30 Symbolic computation and algebraic computation
11Y11 Primality
11Y05 Factorization
11A41 Primes
11A51 Factorization; primality
11G07 Elliptic curves over local fields
11Yxx Computational number theory
PDF BibTeX Cite