Numeri primi: la certezza

Luisella Caire; Umberto Cerruti

Bollettino dell'Unione Matematica Italiana (2007)

  • Volume: 10-A, Issue: 1, page 85-117
  • ISSN: 0392-4041

Abstract

top
Questo articolo fa seguito a quello (pubblicato su un numero precedente del BUMI) in cui abbiamo presentato alcuni algoritmi che studiano se un intero è primo.Mentre nel primo articolo i diversi metodi o erano efficienti ma poco sicuri o avevano, per ragioni varie, possibilità di incertezza, i due algoritmi che descriviamo in questo articolo, quando terminano, danno la certezza che un dato numero è primo. Esaminiamo i metodi ECPP (acronimo per `Elliptic Curve Primality Proving', basato sui gruppi formati dai punti delle curve ellittiche, introdotto e sviluppato da Goldwasser e Kilian nel 1986) e AKS (iniziali di Agrawal - Kayal - Saxena, i nomi dei tre studiosi indiani che lo hanno pubblicato nel 2002). Per comprendere l'algoritmo AKS parliamo di complessità computazionale, delle classi P e NP. Trattiamo anche delle relazioni che AKS ha con alcuni classici test di primalità. Per affrontare ECPP, facciamo alcuni richiami sulle curve ellittiche e sulla loro struttura di gruppo, e descriviamo il certificato di primalità che esso fornisce. Infine accenniamo ad alcuni recenti sviluppi, in particolare al possibile utilizzo simultaneo di ECPP e AKS.

How to cite

top

Caire, Luisella, and Cerruti, Umberto. "Numeri primi: la certezza." Bollettino dell'Unione Matematica Italiana 10-A.1 (2007): 85-117. <http://eudml.org/doc/289671>.

@article{Caire2007,
abstract = {Questo articolo fa seguito a quello (pubblicato su un numero precedente del BUMI) in cui abbiamo presentato alcuni algoritmi che studiano se un intero è primo.Mentre nel primo articolo i diversi metodi o erano efficienti ma poco sicuri o avevano, per ragioni varie, possibilità di incertezza, i due algoritmi che descriviamo in questo articolo, quando terminano, danno la certezza che un dato numero è primo. Esaminiamo i metodi ECPP (acronimo per `Elliptic Curve Primality Proving', basato sui gruppi formati dai punti delle curve ellittiche, introdotto e sviluppato da Goldwasser e Kilian nel 1986) e AKS (iniziali di Agrawal - Kayal - Saxena, i nomi dei tre studiosi indiani che lo hanno pubblicato nel 2002). Per comprendere l'algoritmo AKS parliamo di complessità computazionale, delle classi P e NP. Trattiamo anche delle relazioni che AKS ha con alcuni classici test di primalità. Per affrontare ECPP, facciamo alcuni richiami sulle curve ellittiche e sulla loro struttura di gruppo, e descriviamo il certificato di primalità che esso fornisce. Infine accenniamo ad alcuni recenti sviluppi, in particolare al possibile utilizzo simultaneo di ECPP e AKS.},
author = {Caire, Luisella, Cerruti, Umberto},
journal = {Bollettino dell'Unione Matematica Italiana},
language = {ita},
month = {4},
number = {1},
pages = {85-117},
publisher = {Unione Matematica Italiana},
title = {Numeri primi: la certezza},
url = {http://eudml.org/doc/289671},
volume = {10-A},
year = {2007},
}

TY - JOUR
AU - Caire, Luisella
AU - Cerruti, Umberto
TI - Numeri primi: la certezza
JO - Bollettino dell'Unione Matematica Italiana
DA - 2007/4//
PB - Unione Matematica Italiana
VL - 10-A
IS - 1
SP - 85
EP - 117
AB - Questo articolo fa seguito a quello (pubblicato su un numero precedente del BUMI) in cui abbiamo presentato alcuni algoritmi che studiano se un intero è primo.Mentre nel primo articolo i diversi metodi o erano efficienti ma poco sicuri o avevano, per ragioni varie, possibilità di incertezza, i due algoritmi che descriviamo in questo articolo, quando terminano, danno la certezza che un dato numero è primo. Esaminiamo i metodi ECPP (acronimo per `Elliptic Curve Primality Proving', basato sui gruppi formati dai punti delle curve ellittiche, introdotto e sviluppato da Goldwasser e Kilian nel 1986) e AKS (iniziali di Agrawal - Kayal - Saxena, i nomi dei tre studiosi indiani che lo hanno pubblicato nel 2002). Per comprendere l'algoritmo AKS parliamo di complessità computazionale, delle classi P e NP. Trattiamo anche delle relazioni che AKS ha con alcuni classici test di primalità. Per affrontare ECPP, facciamo alcuni richiami sulle curve ellittiche e sulla loro struttura di gruppo, e descriviamo il certificato di primalità che esso fornisce. Infine accenniamo ad alcuni recenti sviluppi, in particolare al possibile utilizzo simultaneo di ECPP e AKS.
LA - ita
UR - http://eudml.org/doc/289671
ER -

References

top
  1. ADLEMAM, L. M. - HUANG, M. A., Primality Testing and Abelian Varieties Over Finite Fields, Lecture Notes in Mathematics, 1512, Springer-Verlag1992. MR1176511DOI10.1007/BFb0090185
  2. AGRAVAL, M. - KAYAL, N. - SAXENA, N., PRIMES is in P, 2002. MR2123939DOI10.4007/annals.2004.160.781
  3. AGRAVAL, M. - KAYAL, N. - SAXENA, N., PRIMES is in P, Annals of Mathematics, 160 (2004), 781-793. MR2123939DOI10.4007/annals.2004.160.781
  4. AGRAVAL, M. - KAYAL, N. - SAXENA, N., PRIMES is in P, URL: http://www.cse.iitk.ac.in/users/manindra/primalityv6.pdf, 2005.08.11 MR2123939DOI10.4007/annals.2004.160.781
  5. ATKIN, A.O.L. - MORAIN, F., Elliptic curves and primality proving, Mathematics of Computation, 61 (1993), 29-68. Zbl0792.11056MR1199989DOI10.2307/2152935
  6. BERNSTEIN, D. J., Detecting perfect powers in essentially linear time, Mathematics of Computation, 67 (1998), 1253-1283. Zbl0910.11057MR1464141DOI10.1090/S0025-5718-98-00952-1
  7. BERNSTEIN, D. J., Proving primality after Agrawal-Kayal-Saxena, URL: http://cr.yp.to/papers.html#aks, 2003.01.25 
  8. BERNSTEIN, D. J., Proving primality in essential quartic random time, URL: http://cr.yp.to/papers.html#quartic, 2003.01.28, in corso di pubblicazione su Mathematics of Computation. Zbl1144.11085
  9. BERNSTEIN, D. J., Distinguishing prime numbers from composite numbers: the state of the art in 2004, URL: http://cr.yp.to/papers.html#prime2004, 2004.12.23 
  10. BERRIZBEITIA, P., Sharpening Primes is in P for a large family of numbers, Mathematics of Computation, 74 (2005), 2043-2059. Zbl1071.11071MR2164112DOI10.1090/S0025-5718-05-01727-8
  11. CAIRE, L. - CERRUTI, U., Questo numero è primo? Forse sì, dipende..., Bollettino U.M.I. sez. A, la Matematica nella Società e nella Cultura, Serie VIII, Vol. IX-A, Dicembre 2006/1, 449-481. 
  12. CERRUTI, U., Congettura di Riemann e sicurezza mondiale URL: http://alpha01.dm.unito.it/personalpages/cerruti/luglio04-gennaio28.html#riemann 
  13. QI CHENG, Primality Proving via One Round in ECPP and One Iteration in AKS, Lecture Notes in Mathematics, 2729, Springer-Verlag2003. Zbl1122.68456MR2093202DOI10.1007/978-3-540-45146-4_20
  14. DE BRANGES DE BOURCIA, L., Apology for the Proof of the Riemann Hypothesis, 2006.04.25, http://www.math.purdue.edu/branges/apology.pdf 
  15. DE BRANGES DE BOURCIA, L., A proof of the Riemann Hypothesis I, 2005.12.29, http://www.math.purdue.edu/branges/riemannzeta.pdf 
  16. DE BRANGES DE BOURCIA, L., A proof of the Riemann Hypothesis II, 2006.01.11, http://www.math.purdue.edu/branges/riemannII.pdf 
  17. FOUVRY, E., Théorème de Brun-Tichmarsh; application au théorème de Fermat, Invent. Math., 79 (1985), 383-407. MR778134DOI10.1007/BF01388980
  18. GOLDWASSER, S. - KILIAN, J., Almost all primes can be quickly certified, Proceedings of the 18-th Annual ACM Symposium on Theory of Computing, New York, 1986, 316-329. 
  19. GOLDWASSER, S. - KILIAN, J., Primality Testing using Elliptic Curves, Journal of the ACM, 46 (1999), 450-472. Zbl1064.11503MR1812127DOI10.1145/320211.320213
  20. KAYAL, N. - SAXENA, N., Toward a deterministic polynomial time primality tests, URL: http://www.cse.iitk.ac.in/research/btp2002/primality.html, 2002 
  21. LANGUISCO, A. - ZACCAGNINI, A., Introduzione alla Crittografia, Hoepli Editore, Milano, 2004. 
  22. LENSTRA, H. - PILA, J. - POMERANCE, C. (organizers), Future directions in algorithmic number theory, Workshop, March 24-28, 2003, Palo Alto, California, http://www.aimath.org/ARCC/workshops/primesinp.html 
  23. LENSTRA, H. W. - POMERANCE, C., Primality testing with Gaussian Periods, preliminary version, July 2005, URL: http://www.math.dartmouth.edu/carlp/PDF/complexity072805.pdf 
  24. MORAIN, F., Primalité théorique et primalité pratique, ou AKS vs ECPP, 2002, URL: http://www.lix.polytechnique.fr/Labo/Francois.Morain/aks-f.pdf, 2002.10.04 
  25. MORAIN, F., Implementing the asymptotically fast version of the Elliptic Curve Primality Proving Algorithm, 2005, URL: http://www.lix.polytechnique.fr/Labo/Francois.Morain/Articles/fastecpp-final.pdf Zbl1127.11084
  26. MÜLLER, S., On the combined Fermat/Lucas probable prime test, in Crypto and Coding '99, Lecture Notes in Computer Science1746, Springer-Verlag1999 MR1861844DOI10.1007/3-540-46665-7_26
  27. NAIR, M., On Chebyshev-type inequalities for primes, The American Mathematical Monthly, 89 (1982), 126-129. Zbl0494.10004MR643279DOI10.2307/2320934
  28. PANDEY, P. - BHATTACHARJEE, R., Primality testing, Thesis, April 2001, URL: http://www.cse.iitk.ac.in/research/btp2001/primality.ps.gz, 2001 
  29. PRATT, V. R., Every prime has a succinct certificate, SIAM Journal on Computing, 4 (1975), 214-220. Zbl0316.68031MR391574DOI10.1137/0204018
  30. ROTELLA, C., An Efficient Implementation of the AKS Polynomial-Time Primality Proving Algorithm, SCS Undergraduate Thesis (Advisor: Klaus Sutner), Carnegie Mellon, May 2005. 
  31. SCHOOF, R., Elliptic curves over finite fields and the computation of square roots mod p, Math. Computation, 44 (1985), 483-494. Zbl0579.14025MR777280DOI10.2307/2007968
  32. SERAFINI, P., Introduzione alla complessità computazionale, URL:http://www.dimi.uniud.it/serafini/complcomp.pdf 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.