Primality Testing in Polynomial Time From Randomized Algorithms to "PRIMES Is in P" /

• Main Author: Dietzfelbinger, Martin (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Berlin, Heidelberg : Springer Berlin Heidelberg, 2004.
• Series: Lecture Notes in Computer Science, 3000
• Subjects: Mathematics.; Data encryption (Computer science).; Computers.; Algorithms.; Mathematical statistics.; Algebra.; Number theory.; Number Theory.; Algorithm Analysis and Problem Complexity.; Computation by Abstract Devices.; Data Encryption.; Probability and Statistics in Computer Science.

On August 6, 2002,a paper with the title “PRIMES is in P”, by M. Agrawal, N. Kayal, and N. Saxena, appeared on the website of the Indian Institute of Technology at Kanpur, India. In this paper it was shown that the “primality problem”hasa“deterministic algorithm” that runs in “polynomial time”. Find...

Table of Contents:

• 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.