Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P''.
type: Item
instance of: scholarly article
title: Primality testing in polynomial time. From randomized algorithms to ``PRIMES is in P''.
zbMATH Open document ID: 1058.11070
author: Martin Dietzfelbinger
published in: Lecture Notes in Computer Science
publication date: 2004-10-19T00:00:00Z
review text: 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 subj…
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 11-02
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2108707
MaRDI profile type: Publication
full work available at URL: b12334
OpenAlex ID: W2476552886
DOI: 10.1007/B12334
reviewed by: Preda Mihaĭlescu
description: scientific article; zbMATH DE number 2108707