This is a polished introduction to algorithms for performing algebraic operations on a computer, now in its third edition. The algorithms cover a number of problems, primarily in the areas of factoring polynomials and integers, primality testing, fast multiplication, and symbolic integration. It has good coverage of underlying techniques such as Gröbner bases and the Lenstra–Lenstra–Lovász (
The book has a number of shorter discussions on more specialized techniques, such as some special methods for sparse matrices. There are also several short chapters and sections on applications of the main techniques. The book is very well organized and has carefully-chosen numerical examples, which helps manage the complexity of the exposition.
The book concentrates on the mainstream results used in computer algebra systems, without attempting to be comprehensive. For example, it has a chapter on symbolic summation, but for hypergeometric functions this is essentially limited to Gosper summation with only a mention of the more comprehensive Wilf–Zeilberger method.
The book is primarily concerned with exact and symbolic operations. It concentrates on the fastest methods rather than the most straightforward, and provides execution-time analyses for all algorithms. It does not deal with numerical analysis or computer arithmetic. It does not cover work on the intersection of numerical and symbolic work, such as integer relation detection and other techniques important in experimental mathematics.
The book is almost as interesting for the advanced mathematics (mostly in ring and ideal theory and in linear algebra) that is needed to develop the algorithms. It assumes familiarity with the fundamentals of these topics, but does include a 25-page appendix summarizing the needed background. It is well-equipped with exercises, ranging from numerical practice to extensions and variants on results in the body.
Allen Stenger is a math hobbyist and retired software developer. He is webmaster and newsletter editor for the MAA Southwestern Section and is an editor of the Missouri Journal of Mathematical Sciences. His mathematical interests are number theory and classical analysis. He volunteers in his spare time at MathNerds.org, a math help site that fosters inquiry learning.
1. Cyclohexane, cryptography, codes, and computer algebra
Part I. Euclid:
2. Fundamental algorithms
3. The Euclidean Algorithm
4. Applications of the Euclidean Algorithm
5. Modular algorithms and interpolation
6. The resultant and gcd computation
7. Application: decoding BCH codes
Part II. Newton:
8. Fast multiplication
9. Newton iteration
10. Fast polynomial evaluation and interpolation
11. Fast Euclidean Algorithm
12. Fast linear algebra
13. Fourier Transform and image compression
Part III. Gauß:
14. Factoring polynomials over finite fields
15. Hensel lifting and factoring polynomials
16. Short vectors in lattices
17. Applications of basis reduction
Part IV. Fermat:
18. Primality testing
19. Factoring integers
20. Application: public key cryptography
Part V. Hilbert:
21. Gröbner bases
22. Symbolic integration
23. Symbolic summation
25. Fundamental concepts
Sources of illustrations
Sources of quotations
List of algorithms
List of figures and tables
List of notation