Algorithmic number theory, Vol. 1: Efficient algorithms. (English) Zbl 0873.11070

Bach, Eric; Shallit, Jeffrey

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.

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

Keywords:

Legendre symbol; algorithms; complexity; algorithmic number theory; elementary number theory; analytic number theory; probability theory; number theoretical computations; greatest common divisors; arithmetic in residue class rings; Jacobi symbol; arithmetic of finite fields; roots; factoring of polynomials; Hensel’s lemma; primality testing