Primality Testing in Polynomial Time
From Randomized Algorithms to "PRIMES Is in P"
Buch in deiner Nähe kaufen
Beschreibung
A self-contained treatment of theoretically and practically important efficient algorithms for the primality problem, covering the randomized algorithms by Solovay-Strassen and Miller-Rabin from the late 1970s as well as the recent deterministic algorithm of Agrawal, Kayal, and Saxena. The volume is written for students of computer science, in particular those with a special interest in cryptology, and students of mathematics. The text may be used as a supplement for courses or for self-study.
Describes the new deterministic polynomial time primality test (Agrawal/Kayal/Saxena) with complete analysis in a consolidated way Includes supplementary material: sn.pub/extras
Autor*in
Martin Dietzfelbinger
Themen in »Primality Testing in Polynomial Time«
Prime algorithm algorithmics algorithms computer computer science algorithm analysis and problem complexity
Stimmen zu »Primality Testing in Polynomial Time«
From the reviews:
"This book gives an account of the recent proof by M. Agrawal, N. Kayal and N. Saxena … that one can decide in polynomial time whether a given natural number is prime or composite. … It presents the background needed from number theory and algebra to make the proof accessible to undergraduates. … This concise book is written for students of computer science and of mathematics." (Samuel S. Wagstaff, Mathematical Reviews, Issue 2005 m)
"The book can logically be separated into two parts: the first covering introductory material and the second covering the AKS result itself. … Chapters … are a joy to read, and I found the proofs and explanations clear and concise. Amazingly, the material is presented in full, with complete proofs given for all results necessary for proving the main results of the book. … I would enthusiastically and wholeheartedly recommend this book … ." (Jonathan Katz, SIGACT News, Vol. 37 (1), 2006)
()