Modern Computer Algebra

by Joachim von zur Gathen and Jürgen Gerhard
Cambridge University Press, 1999, 754 pages, ISBN 0-521-64176-4
Authors' web page

This is a fairly heavy-duty book. It represents maybe a year's worth of study for a math / comp.sci. late undergrad / early graduate student. A software engineer looking for cookbook algorithms to solve math problems should probably look elsewhere. There are only two sections specifically about implementation: 9.7 about implementing fast arithmetic, and 15.7 about implementing factorization. These are certainly interesting, but the focus of the book is definitely on theory. However, if you work through the notation and understand the math, the algorithms are here, and generally more detailed and up-to-date than, say, Knuth's Seminumerical Algorithms.

There are a few things you need to know before you tackle the book:

The book has an interesting structure. It's broken into sections named for five of the giants of math:

Basic polynomial and multi-precision arithmetic; GCDs and the Euclidean Algorithm; modular arithmetic, modular inverses; the Chinese Remainder Algorithm.
Fast multiplication; Newton iteration; faster Euclidean Algorithm, matrix multiplication, and polynomial evaluation; the Discrete Fourier Transform and the Fast Fourier Transform.
Factoring polynomials.
Primality testing; factoring integers; public-key cryptography.
Gröbner bases (whatever they are!); symbolic integration; symbolic summation.
This sort of half works and half doesn't, in that these men all did a whole lot of other things besides these. But it's certainly a nice nod to history.

Overall, the book seems like a great advanced textbook, and a reasonably good reference work to be used in combination with a few other references such as the aforementioned Knuth, Schneier's Applied Cryptography, Sedgewick's classic Algorithms, and so on. It is also beautifully produced and a pleasure to read, even when the subject is over my head.

Order it from
Back to Reviews Page.
Back to Jef's Web Page.