##
**Modern computer algebra.**
*(English)*
Zbl 0936.11069

Cambridge: Cambridge University Press. xiii, 753 p. (1999).

As indicated in the Introduction, the aim of the authors of this book is triple: give rather complete information on the mathematical tools and results used, analyze the asymptotic cost of the algorithms and propose asymptotically fast methods. They reach completely this triple objective. This fact distinguishes this book from the preceding ones in the same domain which either focus on the mathematical point of view, or are mainly user-oriented.

This book contains more than seven hundred pages and five main sections, each section is given the name of a famous mathematician: Euclid, Newton, Fermat, Gauß and Hilbert. Of course, the part “Euclid” contains the Euclidean algorithm and also a very detailed study of modular calculus and its applications, resultant computation, and application for decoding BCH codes. The section “Newton” contains the presentation of fast algorithms for the elementary arithmetical operations, the fast Fourier transform algorithm (FFT), interpolation, … The elementary arithmetics: primality tests, factorization of integers, applications to cryptography (RSA method) is the part “Fermat”. The chapters linked to Gauss are: factorization of polynomials over finite fields, Hensel lifting lemma and factoring polynomials with integer coefficients, search of small vectors in lattices (LLL method) and applications. The last part, “Hilbert”, contains the study of Gröbner bases, symbolic summation, symbolic integration, and applications. There is also an Appendix on fundamental concepts such as elementary algebraic structures, linear algebra, finite fields, finite probability spaces and complexity theory.

Each chapter contains numerous examples which are very instructive, the pseudo-code of the algorithms, exercises and very complete and interesting historical notes. The cost of the algorithms is studied in great detail and the authors give comments on the efficiency of these algorithms and their present practical limits.

The style is very clear. The arguments are very precise. In my opinion, the level of presentation is convenient for graduate students, some parts are quite readable for good undergraduate students. The typography and the quality of illustration of this Cambridge book are splendid.

To conclude, I find the quality of this book really exceptional, this is certainly an excellent source on the state of the art in Computer Algebra, just before 2000.

This book contains more than seven hundred pages and five main sections, each section is given the name of a famous mathematician: Euclid, Newton, Fermat, Gauß and Hilbert. Of course, the part “Euclid” contains the Euclidean algorithm and also a very detailed study of modular calculus and its applications, resultant computation, and application for decoding BCH codes. The section “Newton” contains the presentation of fast algorithms for the elementary arithmetical operations, the fast Fourier transform algorithm (FFT), interpolation, … The elementary arithmetics: primality tests, factorization of integers, applications to cryptography (RSA method) is the part “Fermat”. The chapters linked to Gauss are: factorization of polynomials over finite fields, Hensel lifting lemma and factoring polynomials with integer coefficients, search of small vectors in lattices (LLL method) and applications. The last part, “Hilbert”, contains the study of Gröbner bases, symbolic summation, symbolic integration, and applications. There is also an Appendix on fundamental concepts such as elementary algebraic structures, linear algebra, finite fields, finite probability spaces and complexity theory.

Each chapter contains numerous examples which are very instructive, the pseudo-code of the algorithms, exercises and very complete and interesting historical notes. The cost of the algorithms is studied in great detail and the authors give comments on the efficiency of these algorithms and their present practical limits.

The style is very clear. The arguments are very precise. In my opinion, the level of presentation is convenient for graduate students, some parts are quite readable for good undergraduate students. The typography and the quality of illustration of this Cambridge book are splendid.

To conclude, I find the quality of this book really exceptional, this is certainly an excellent source on the state of the art in Computer Algebra, just before 2000.

Reviewer: Maurice Mignotte (Strasbourg)

### MSC:

11Yxx | Computational number theory |

68W30 | Symbolic computation and algebraic computation |

68-01 | Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science |

13P05 | Polynomials, factorization in commutative rings |

11Y16 | Number-theoretic algorithms; complexity |

12Y05 | Computational aspects of field theory and polynomials (MSC2010) |

11Y05 | Factorization |

11Y11 | Primality |

### Keywords:

computer algebra; asymptotic cost of algorithms; asymptotically fast methods; Euclidean algorithm; modular calculus; resultant computation; fast Fourier transform algorithm; interpolation; primality tests; factorization of integers; cryptography; RSA method; factorization of polynomials over finite fields; Hensel lifting lemma; LLL method; Gröbner bases; symbolic summation; symbolic integration; complexity
PDF
BibTeX
XML
Cite

\textit{J. von zur Gathen} and \textit{J. Gerhard}, Modern computer algebra. Cambridge: Cambridge University Press (1999; Zbl 0936.11069)

### Online Encyclopedia of Integer Sequences:

a(n) is the number of pairs (x,y) with 1 <= x, y <= 10^n and gcd(x,y)=1.Number of ordered triples (x, y, z) with gcd(x, y, z) = 1 and 1 <= {x, y, z} <= 10^n.

Number of ordered quadruples (w, x, y, z) with gcd(w, x, y, z) = 1 and 1 <= {w, x, y, z} <= 10^n.

Number of ordered 5-tuples (v,w, x, y, z) with gcd(v, w, x, y, z) = 1 and 1 <= {v, w, x, y, z} <= 10^n.

Number of ordered 6-tuples (a,b,c,d,e,f) with gcd(a,b,c,d,e,f)=1 (1<= {a,b,c,d,e,f} <= n).