zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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. $ 46.50 (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:
11YxxComputational number theory
11-02Research monographs (number theory)
68Q25Analysis of algorithms and problem complexity
11Y05Factorization
11Y11Primality
11Y16Algorithms; complexity (number theory)
11Y40Algebraic number theory computations
11T06Polynomials over finite fields or rings
11A05Multiplicative structure of the integers
11A41Elementary prime number theory
11-04Machine computation, programs (number theory)