Modern Computer Algebra

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 authors are both German-speakers. I don't think the book was actually written in German and translated, but there are a few remnants of Germanness. In particular, they occasionally use ß instead of ss. For example, Gauß instead of Gauss. Just remember that these two are equivalent.
• As soon as you get to chapter 3, the algebra and set notation starts in. Put a bookmark on page 728, where there's a convenient notation cheat sheet. Read through it once carefully and then refer to it as necessary.
• Also towards the back of the book is the appendix, chapter 25, "Fundamental concepts". You should skim this before looking at the rest of the book. If the concepts don't look at least vaguely familiar, you'll get lost pretty fast.

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

Euclid:

Basic polynomial and multi-precision arithmetic; GCDs and the Euclidean Algorithm; modular arithmetic, modular inverses; the Chinese Remainder Algorithm.

Newton:

Fast multiplication; Newton iteration; faster Euclidean Algorithm, matrix multiplication, and polynomial evaluation; the Discrete Fourier Transform and the Fast Fourier Transform.

Gauss:

Factoring polynomials.

Fermat:

Primality testing; factoring integers; public-key cryptography.

Hilbert:

Gröbner bases (whatever they are!); symbolic integration; symbolic summation.

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 Amazon.com. Back to Reviews Page.
Back to Jef's Web Page.