Skip to main content
SpringerLink
Log in
Book cover

Primality Testing in Polynomial Time

From Randomized Algorithms to "PRIMES Is in P"

  • Textbook
  • © 2004

Overview

Authors:
  1. Martin Dietzfelbinger

    1. Technische Universität Ilmenau, Ilmenau, Germany

    View author publications

    You can also search for this author in PubMed   Google Scholar

  • Describes the new deterministic polynomial time primality test (Agrawal/Kayal/Saxena) with complete analysis in a consolidated way
  • Includes supplementary material: sn.pub/extras

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 3000)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (9 chapters)

  1. Front Matter

    Download chapter PDF

  2. 1. Introduction: Efficient Primality Testing

    • Martin Dietzfelbinger
    Pages 1-12

  3. 2. Algorithms for Numbers and Their Complexity

    • Martin Dietzfelbinger
    Pages 13-21

  4. 3. Fundamentals from Number Theory

    • Martin Dietzfelbinger
    Pages 23-53

  5. 4. Basics from Algebra: Groups, Rings, and Fields

    • Martin Dietzfelbinger
    Pages 55-71

  6. 5. The Miller-Rabin Test

    • Martin Dietzfelbinger
    Pages 73-84

  7. 6. The Solovay-Strassen Test

    • Martin Dietzfelbinger
    Pages 85-94

  8. 7. More Algebra: Polynomials and Fields

    • Martin Dietzfelbinger
    Pages 95-114

  9. 8. Deterministic Primality Testing in Polynomial Time

    • Martin Dietzfelbinger
    Pages 115-131

  10. A. Appendix

    • Martin Dietzfelbinger
    Pages 133-142

  11. Back Matter

    Download chapter PDF
Back to top

Keywords

About this book

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”. Finding out whether a given number n is a prime or not is a problem that was formulated in ancient times, and has caught the interest of mathema- ciansagainandagainfor centuries. Onlyinthe 20thcentury,with theadvent of cryptographic systems that actually used large prime numbers, did it turn out to be of practical importance to be able to distinguish prime numbers and composite numbers of signi?cant size. Readily, algorithms were provided that solved the problem very e?ciently and satisfactorily for all practical purposes, and provably enjoyed a time bound polynomial in the number of digits needed to write down the input number n. The only drawback of these algorithms is that they use “randomization” — that means the computer that carries out the algorithm performs random experiments, and there is a slight chance that the outcome might be wrong, or that the running time might not be polynomial. To ?nd an algorithmthat gets by without rand- ness, solves the problem error-free, and has polynomial running time had been an eminent open problem in complexity theory for decades when the paper by Agrawal, Kayal, and Saxena hit the web.

Reviews

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)

Authors and Affiliations

  • Technische Universität Ilmenau, Ilmenau, Germany

    Martin Dietzfelbinger

About the author

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.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation