zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
Primality testing in polynomial time. From randomized algorithms to “PRIMES is in P”. (English) Zbl 1058.11070
Lecture Notes in Computer Science 3000. Berlin: Springer (ISBN 3-540-40344-2/pbk). x, 147 p. EUR 24.95/net; sFr 45.50; £ 19.00; $ 34.95 (2004).

The nice short book is a just in time reaction to the discovery of a polynomial time primality test by M. Agarwal, N. Kayal and N. Saxena [Ann. Math. (2) 160, No. 2, 755–779 (2004; Zbl 1071.11070) (AKS)]. The book is dedicated to a large public with mathematical interest, computer scientists first of all. As such, the book carries a well designed program of self-containment. Thus, the reader is offered a guided tour through various fields of mathematics. The topics presented require a minimal background of algebra and analysis, are carefully elaborated and focus unperceptibly towards the short final culmination: the description and the proof of the primality test AKS.

The topics developed in the book start with basics of complexity theory. It goes on with some elements of number theory – the Euclidean Algorithm, modular arithmetic and the Chinese Remainder Theorem. However, along with these elements which are fundamental for any algorithmic application of number theory, there is also a lovely presentation of Chebyshev’s approximation theorem for the Prime Density Theorem: this is in the end how much one needs to know about prime density in the proof of AKS. The introduction continues with fundamentals of algebra, finite fields, etc. and a generous presentation of the main probabilistic primality tests: Rabin-Miller (strong pseudo primality test) and Solvay-Strassen.

Finally, in the last fifteen pages, the AKS-Test is presented along with an almost complete proof. Since the later developments by Lenstra and Pomerance are only mentioned but not included in the material of the book, the proof follows closely the initial proof of Agarwal et al. In particular, the strong number theoretical result of Fouvry is required, and a proof of this result is certainly beyond the frame of this book. I believe this is also the only exception to the goal of self-containment followed by the author.

Altogether, an enchanting reading for people interested in the subject.

11-02Research monographs (number theory)
11Y16Algorithms; complexity (number theory)
68Q15Complexity classes of computation
68Q25Analysis of algorithms and problem complexity