Dietzfelbinger Primality Testing in Polynomial Time

From Randomized Algorithms to "PRIMES Is in P"
2004
ISBN: 978-3-540-25933-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 3000, 150 Seiten, eBook

Reihe: Lecture Notes in Computer Science

A self-contained treatment of theoretically and practically important efficient algorithms for the primality problem. The text covers 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, and it may be used as a supplement for courses or for self-study.

Zielgruppe

Research

Autoren/Hrsg.

Dietzfelbinger, Martin

Inhaltsverzeichnis

1. Introduction: Efficient Primality Testing.- 2. Algorithms for Numbers and Their Complexity.- 3. Fundamentals from Number Theory.- 4. Basics from Algebra: Groups, Rings, and Fields.- 5. The Miller-Rabin Test.- 6. The Solovay-Strassen Test.- 7. More Algebra: Polynomials and Fields.- 8. Deterministic Primality Testing in Polynomial Time.- A. Appendix.

Über Autor(innen)

Univ.-Prof. Dr.(USA) Martin Dietzfelbinger (b. 1956) studied Mathematics in Munich and earned his Ph.D. from the University of Illinois at Chicago. In 1992, he obtained his Habilitation at the Universität Paderborn with a thesis on randomized algorithms; in the same year he became a professor of computer science at the Universität Dortmund. Since 1998, he holds the chair for Complexity Theory and Efficient Algorithms at the Faculty of Computer Science and Automation of the Technische Universität Ilmenau, Germany. His main research interests are in complexity theory and data structures.