LEADER 04111nam  22007215  450 
001 9910768476103321
005 20230810201048.0
010   $a9783540259336 (e-book)
010   $a9783540403449 (pbk.)
024 7 $a10.1007/b12334
035   $a(MiAaPQ)EBC3088715
035   $a(DE-He213)978-3-540-25933-6
035   $a(PPN)155228897
035   $a(CKB)1000000000212164
035   $a(EXLCZ)991000000000212164
100   $a20121227d2004      u|         0
101 0 $aeng
135   $aur|n|---|||||
181   $ctxt$2rdacontent
182   $cc$2rdamedia
183   $acr$2rdacarrier
200 10$aPrimality Testing in Polynomial Time $eFrom Randomized Algorithms to "PRIMES Is in P" /$fby Martin Dietzfelbinger
205   $a1st ed. 2004.
210  1$aBerlin, Heidelberg :$cSpringer Berlin Heidelberg :$cImprint: Springer,$d2004.
215   $a1 online resource (x, 147 p.)
225 1 $aLecture Notes in Computer Science,$x1611-3349 ;$v3000
320   $aIncludes bibliographical references and index.
327   $a1. 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.
330   $aOn 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.
410  0$aLecture Notes in Computer Science,$x1611-3349 ;$v3000
606   $aNumber theory
606   $aAlgebra
606   $aAlgorithms
606   $aComputer science
606   $aCryptography
606   $aData encryption (Computer science)
606   $aComputer science$xMathematics
606   $aMathematical statistics
606   $aNumber Theory
606   $aAlgebra
606   $aAlgorithms
606   $aTheory of Computation
606   $aCryptology
606   $aProbability and Statistics in Computer Science
615  0$aNumber theory.
615  0$aAlgebra.
615  0$aAlgorithms.
615  0$aComputer science.
615  0$aCryptography.
615  0$aData encryption (Computer science)
615  0$aComputer science$xMathematics.
615  0$aMathematical statistics.
615 14$aNumber Theory.
615 24$aAlgebra.
615 24$aAlgorithms.
615 24$aTheory of Computation.
615 24$aCryptology.
615 24$aProbability and Statistics in Computer Science.
676   $a512.942
700   $aDietzfelbinger$b Martin$0488533
912   $a9910768476103321
996   $aPrimality testing in polynomial time$9287435
997   $aUNINA