Algorithmic number theory, Vol. 1: Efficient algorithms.

*(English)*Zbl 0873.11070
MIT Press Series in the Foundations of Computing. Cambridge, MA: The MIT Press. xvi, 512 p. (1996).

This book is the first volume of a projected two-volume set on algorithmic number theory. It appears in a series on theoretical computer science and therefore the emphasis is on algorithms and their complexity. The main emphasis in on problems in elementary number theory. However, methods from analytic number theory, algebraic number theory and probability theory are involved at various places. The present volume is dedicated to problems for which (relatively) efficient solutions are known.

There are nine chapters, including a large number of exercises (the solutions of most of them are sketched in an appendix). The authors give more than 1750 citations and a variety of (historical) remarks on their topics. The first chapter contains an overview on number theory and the development of number theoretical computations. It is followed by basics on elementary number theory and some elements of analytic number theory. Chapter 3 is an introductory survey on complexity theory describing various models.

In chapters 4 to 6 the authors present the computation of greatest common divisors (probably the most discussed algorithm in number theory), algorithms for doing arithmetic in residue class rings of the rational integers (including the Legendre and Jacobi symbol), and the arithmetic of finite fields.

The final chapters 6 to 9 cover the solution of equations over finite fields (the calculation of roots, factoring of polynomials, Hensel’s lemma), facts and heuristics on prime numbers, and “basic” tool for primality testing.

The book is well written, and the authors treat their topics concisely with up-to-date methods. It not only contains algorithms and their complexity, but also provides the reader with a lot of additional information about the development of the underlying theory and practical computations. It is certainly to be recommended to all people interested in computational number theory. In my opinion it is probably the best treatment of algorithmic elementary number theory from the viewpoint of theoretical computer science.

What I find a little disturbing is that the authors give the impression that they present all existing important algorithms. Here I clearly miss the primality test of Atkin/Morain which is superior to the method using Gaussian sums that is discussed in detail. The effort of the authors to cover all areas also leads to grotesquely false remarks on computer algebra systems for number theory. Unfortunately, the numerous citations are not always reliable.

There are nine chapters, including a large number of exercises (the solutions of most of them are sketched in an appendix). The authors give more than 1750 citations and a variety of (historical) remarks on their topics. The first chapter contains an overview on number theory and the development of number theoretical computations. It is followed by basics on elementary number theory and some elements of analytic number theory. Chapter 3 is an introductory survey on complexity theory describing various models.

In chapters 4 to 6 the authors present the computation of greatest common divisors (probably the most discussed algorithm in number theory), algorithms for doing arithmetic in residue class rings of the rational integers (including the Legendre and Jacobi symbol), and the arithmetic of finite fields.

The final chapters 6 to 9 cover the solution of equations over finite fields (the calculation of roots, factoring of polynomials, Hensel’s lemma), facts and heuristics on prime numbers, and “basic” tool for primality testing.

The book is well written, and the authors treat their topics concisely with up-to-date methods. It not only contains algorithms and their complexity, but also provides the reader with a lot of additional information about the development of the underlying theory and practical computations. It is certainly to be recommended to all people interested in computational number theory. In my opinion it is probably the best treatment of algorithmic elementary number theory from the viewpoint of theoretical computer science.

What I find a little disturbing is that the authors give the impression that they present all existing important algorithms. Here I clearly miss the primality test of Atkin/Morain which is superior to the method using Gaussian sums that is discussed in detail. The effort of the authors to cover all areas also leads to grotesquely false remarks on computer algebra systems for number theory. Unfortunately, the numerous citations are not always reliable.

Reviewer: M.Pohst (Berlin)

##### MSC:

11Yxx | Computational number theory |

11-02 | Research exposition (monographs, survey articles) pertaining to number theory |

68Q25 | Analysis of algorithms and problem complexity |

11Y05 | Factorization |

11Y11 | Primality |

11Y16 | Number-theoretic algorithms; complexity |

11Y40 | Algebraic number theory computations |

11T06 | Polynomials over finite fields |

11A05 | Multiplicative structure; Euclidean algorithm; greatest common divisors |

11A41 | Primes |

11-04 | Software, source code, etc. for problems pertaining to number theory |