000 04002nam a22006495i 4500
001 978-3-540-25933-6
003 DE-He213
005 20240423130118.0
007 cr nn 008mamaa
008 121227s2004 gw | s |||| 0|eng d
020 _a9783540259336
_9978-3-540-25933-6
024 7 _a10.1007/b12334
_2doi
050 4 _aQA241-247.5
072 7 _aPBH
_2bicssc
072 7 _aMAT022000
_2bisacsh
072 7 _aPBH
_2thema
082 0 4 _a512.7
_223
100 1 _aDietzfelbinger, Martin.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
245 1 0 _aPrimality Testing in Polynomial Time
_h[electronic resource] :
_bFrom Randomized Algorithms to "PRIMES Is in P" /
_cby Martin Dietzfelbinger.
250 _a1st ed. 2004.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2004.
300 _aX, 150 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v3000
505 0 _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.
520 _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.
650 0 _aNumber theory.
650 0 _aAlgebra.
650 0 _aAlgorithms.
650 0 _aComputer science.
650 0 _aCryptography.
650 0 _aData encryption (Computer science).
650 0 _aComputer science
_xMathematics.
650 0 _aMathematical statistics.
650 1 4 _aNumber Theory.
650 2 4 _aAlgebra.
650 2 4 _aAlgorithms.
650 2 4 _aTheory of Computation.
650 2 4 _aCryptology.
650 2 4 _aProbability and Statistics in Computer Science.
710 2 _aSpringerLink (Online service)
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783540403449
776 0 8 _iPrinted edition:
_z9783662174456
830 0 _aLecture Notes in Computer Science,
_x1611-3349 ;
_v3000
856 4 0 _uhttps://doi.org/10.1007/b12334
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
912 _aZDB-2-BAE
942 _cSPRINGER
999 _c185180
_d185180