It’s a pleasure to find a book that is so masterful and so well written that it has all the hallmarks of a classic. This is such a book. Shoup set himself the difficult task of bringing readers up to speed with number theory and algebra, starting “from scratch” (he is quite successful). My main complaint is that the book is not longer, but as Shoup regretfully observes in the introduction, some important topics were omitted to keep the book a reasonable size.

Many books on computational number theory present the theory as a sort of smorgasbord of algorithms: primality testing, factorization, discrete logarithms, modular square, and nth roots. Shoup steers clear of this recipe approach and, instead, places the entire theory into a formal algebraic setting. This allows not only for elegance of exposition and remarkable clarity, but also provides the entire book with structural homogeneity.

Even though “some topics could simply not be covered,” it manages to include a wide range of topics. The book is geared toward students of cryptography and coding theory, as it covers the most relevant material in those disciplines.

The book starts with several standard integer-based number theory concepts: divisibility; congruences and modular arithmetic, including quadratic residues (but reciprocity is treated later); large integer arithmetic; Euclid’s algorithm and its association with the Chinese remainder theorem; and a brief discussion of the RSA cryptosystem, including a particularly elegant proof of its correctness. All of this material is standard for many other texts, yet it is rarely treated with as much care as here, in spite of the relative brevity. The first few chapters contain as much mathematics as many other entire cryptography texts and yet, at this stage, we are not even one fifth into the book. Another chapter discusses the distribution of primes, including a proof of Bertrand’s postulate and a discussion of the prime number theorem. Given the importance of primes to modern cryptography, these are vital topics, so it is refreshing to see them treated so carefully.

These first chapters set the scene, so to speak, for the number theory with which the text is concerned. However, much of the subsequent material is discussed in terms of the general theory of groups and rings. Primitive roots, for example, are not discussed as such, but in terms of generators of the nonzero residues of integers modulo a prime. Although this approach might seem at first to be unnecessarily obtuse, it is in fact the most natural way to introduce these algorithms, as it places them squarely in a generalized algebraic theory. The text, as one would expect, contains several chapters that discuss the basic theory of abelian groups and rings, including a fine proof of the fundamental theorem of the structure of finite abelian groups as sums of cyclic groups.

What makes this book unique is the way in which several different mathematical strands--number theory and algebra--are interwoven and made into a masterful whole. Apart from rings and fields, there is much linear algebra (modules, vector spaces, and matrices), as well as a considerable amount of probability distributions and probabilistic algorithms, culminating in the Miller-Rabin test for primality and a few applications.

The book ends with some chapters on finite fields and their various algorithms and a chapter on the Agrawal-Kayal-Saxena (AKS) deterministic primality test; the author carefully observes that the probabilistic Miller-Rabin test is much faster than AKS and, hence, should be preferred for all practical purposes. Nonetheless, as an ingenious use of much number theory and algebra, the AKS algorithm is a lovely example with which to finish the text.

Although the text does not require much specific mathematical background, I would hesitate to use it except in an advanced class, or with students whose mathematical ability is already high. The material moves swiftly--while never compromising rigor--and the multiple strands assume considerable ability on the part of the reader. I was pleased to see copious exercises; a student who has completed the book and mastered the exercises will be in a very strong position to embark on some advanced studies. The author does not recommend any specific chapter sequence for a semester’s study, but an astute teacher could pull some parts from this text for an initial course of study, and then complete the text in an advanced course.

One regrettable omission is computational tools--neither Shoup’s own C++ NTL library for computational number theory and algebra nor a computer algebra system. A companion volume, or some material on the author’s Web site that discusses some implementation issues, would be most welcome. (Note: the entire text is available under a Creative Commons license on the author’s Web site (http://www.shoup.net/).

This is a truly magnificent text, deserving of a place on the shelves of any mathematician or computer scientist working in these areas.