Primality testing in polynomial time : from randomized algorithms to "PRIMES is in P"
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...
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Livre numérique |
| Langue: | Anglais |
| Publié: |
Berlin [etc.] :
Springer
[20..].
Cham : Springer Nature |
| Collection: | Lecture notes in computer science
3000 |
| Sujets: | |
| Accès en ligne: | Accès sur la plateforme de l'éditeur Accès sur la plateforme Istex Accès Université d'Orléans Accès INSA CVL |
| Note: |
Archives Springer e-books (Licence nationale) Archives Springer e-books (Licence nationale) |
| Autres localisations: | Voir dans le Sudoc |
| Edition sous un autre format: | • Primality testing in polynomial time, from randomized algorithms to "PRIMES is in P", Martin Dietzfelbinger, 2004, Berlin, Springer, 1 vol. (X-147 p.), Lecture notes in computer science, 3-540-40344-2 • Primality Testing in Polynomial Time, Texte imprimé, 9783662174456 |
| LEADER | 04080nam a22004337a 4500 | ||
|---|---|---|---|
| 001 | 972721 | ||
| 008 | 110927q2000 xxe ||| |||| 00| 0 eng d | ||
| 009 | PPN155228897 | ||
| 020 | |a 9783540259336 (PDF) | ||
| 041 | 0 | |a eng | |
| 082 | |a 004 | ||
| 082 | |a 512.942 | ||
| 100 | 1 | |a Dietzfelbinger, Martin. | |
| 245 | 1 | 0 | |a Primality testing in polynomial time : |b from randomized algorithms to "PRIMES is in P" |c Martin Dietzfelbinger. |
| 260 | |a Berlin [etc.] : |b Springer. | ||
| 260 | |a Cham : |b Springer Nature, |c [20..]. | ||
| 490 | 0 | |a Lecture notes in computer science |v 3000 |x 1611-3349 | |
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 500 | |a Archives Springer e-books (Licence nationale) | ||
| 505 | 0 | |a 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. | |
| 506 | |a Accès en ligne pour les établissements français bénéficiaires des licences nationales | ||
| 506 | |a Accès soumis à abonnement pour tout autre établissement | ||
| 506 | |a Conditions particulières de réutilisation pour les bénéficiaires des licences nationales. https://www.licencesnationales.fr/springer-nature-ebooks-contrat-licence-ln-2017 | ||
| 520 | |a 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. | ||
| 650 | |a Modèles mathématiques | ||
| 650 | |a Informatique | ||
| 650 | |a Cryptographie | ||
| 650 | |a Algorithmes | ||
| 650 | |a Chiffrement (informatique) | ||
| 650 | |a Nombres, Théorie des | ||
| 650 | |a Polynômes | ||
| 650 | |a Nombres premiers | ||
| 776 | 0 | |0 08118008X |t Primality testing in polynomial time |o from randomized algorithms to "PRIMES is in P" |f Martin Dietzfelbinger |d 2004 |c Berlin |n Springer |p 1 vol. (X-147 p.) |s Lecture notes in computer science |z 3-540-40344-2 | |
| 776 | 0 | |t Primality Testing in Polynomial Time |b Texte imprimé |z 9783662174456 | |
| 856 | 4 | |q PDF |u https://doi.org/10.1007/b12334 |z Accès sur la plateforme de l'éditeur | |
| 856 | 4 | |u https://revue-sommaire.istex.fr/ark:/67375/8Q1-7FJKM83W-P |z Accès sur la plateforme Istex | |
| 856 | 4 | |5 452349901:750633638 |u https://ezproxy.univ-orleans.fr/login?url=https://doi.org/10.1007/b12334 |z Accès Université d'Orléans | |
| 856 | 4 | |5 180339901:753990008 |u https://ezproxy.insa-cvl.fr/login?qurl=https://doi.org/10.1007/b12334 |z Accès INSA CVL | |
| 997 | |0 972721 |1 Livre numérique |a Ressource numérique |b INSA |b ENSA |c 0/Bibliothèque numérique/ |c 1/Bibliothèque numérique/Autre ressource numérique/ | ||