Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P''. (Q1882154)

The nice short book is a just in time reaction to the discovery of a polynomial time primality test by \textit{M. Agarwal, N. Kayal} and \textit{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.