Book Review: "A Computational Introduction to Number Theory and Algebra" by Victor Shoup, 2nd ed.

I wrote this review a few months ago for “Computing Reviews”, who’ve published it. But for the benefit of those who don’t have access to these reviews, here it is.

---

Occasionally it’s a pleasure to find a book which is so masterful, so well written, that it has all the hallmarks of the classic. This is such a book. Shoup has set himself a difficult task – to bring the reader up to speed with number theory and algebra, starting “from scratch” – and he has succeeded magnificently. My main complaint with the book is that it is not longer, but as Shoup himself regretfully observes in the introduction, to keep to a reasonable size, some important topics had to be omitted.

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

Even though “some topics could simply not be covered”, the range of topics presented is wide. The book is geared towards students of cryptography and coding theory, and the material has been chosen to be most relevant to those disciplines.

The books starts with several of standard integer based number theory: 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 this material is standard to many other texts, yet rarely treated with as much care as here, in spite of the relative brevity. These first few chapters contain as much mathematics as many cryptography texts, and yet at this stage we are not yet 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 may be considered vital topics, and it is refreshing to see them treated so well.

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 non-zero 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 of introducing these algorithms, as it places them squarely in a generalized algebraic theory. The text, as we would expect, contains several chapters discussing the basic theory of abelian groups and rings, including a fine proof of the fundamental theorem of the structure of finite abelian groups as
a sum of cyclic groups.

What makes this book unique is the way that several different mathematical strands – number theory and algebra – are interwoven and made into a masterful whole. As well as rings and fields, there is much linear algebra (modules, vector spaces and matrices), as well as a considerable amount on 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 AKS deterministic primality test, for which the author carefully observes that the probabilistic Miller-Rabin test is much faster, and hence should be preferred for all practical purposes. However, 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 requires not much specific mathematical background, I would hesitate to use it except in an advanced class, or for students whose mathematical ability was already high. The material moves swiftly – while never compromising rigour – 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 sequences for a semester’s study, but clearly an astute teacher could pull some parts from this text for an initial course of study, and complete the text in an advanced course.

One regrettable omission is that of the use of any computational tools, either the author’s own C++ NTL library for computational number theory and algebra, or the use of a computer algebra system. A companion volume, or material on the author’s website, discussing some implementation issues, would be most welcome. We note in passing that thanks to the generosity of the publishers, the entire text is available under a Creative Commons licence on the author’s 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. I hope it has a long life and many further editions.

About these ads