Willkommen, schön sind Sie da!
Logo Ex Libris

Primality Testing in Polynomial Time

  • Kartonierter Einband
  • 164 Seiten
(0) Erste Bewertung abgeben
Alle Bewertungen ansehen
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 In... Weiterlesen
72.00 CHF 57.60
Sie sparen CHF 14.40
Print on Demand - Auslieferung erfolgt in der Regel innert 4 bis 6 Wochen.
Bestellung & Lieferung in eine Filiale möglich


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

Describes the new deterministic polynomial time primality test (Agrawal/Kayal/Saxena) with complete analysis in a consolidated way


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.

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.


Titel: Primality Testing in Polynomial Time
Untertitel: From Randomized Algorithms to "PRIMES Is in P"
EAN: 9783540403449
ISBN: 3540403442
Format: Kartonierter Einband
Herausgeber: Springer Berlin Heidelberg
Genre: Informatik
Anzahl Seiten: 164
Gewicht: 260g
Größe: H235mm x B155mm x T9mm
Jahr: 2004
Untertitel: Englisch
Auflage: 2004

Weitere Produkte aus der Reihe "Lecture Notes in Computer Science"