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.
@article{BUMI_2007_8_10A_1_85_0,
author = {Luisella Caire and Umberto Cerruti},
title = {Numeri primi: la certezza},
journal = {Bollettino dell'Unione Matematica Italiana},
volume = {10-A},
year = {2007},
pages = {85-117},
zbl = {1277.11114},
mrnumber = {2320482},
language = {it},
url = {http://dml.mathdoc.fr/item/BUMI_2007_8_10A_1_85_0}
}
Caire, Luisella; Cerruti, Umberto. Numeri primi: la certezza. Bollettino dell'Unione Matematica Italiana, Tome 10-A (2007) pp. 85-117. http://gdmltest.u-ga.fr/item/BUMI_2007_8_10A_1_85_0/
[1] - , Primality Testing and Abelian Varieties Over Finite Fields, Lecture Notes in Mathematics, 1512, Springer-Verlag 1992. | MR 1176511
[2] - - , PRIMES is in P, 2002. | MR 2123939
[3] - - , PRIMES is in P, Annals of Mathematics, 160 (2004), 781-793. | MR 2123939
[4] - - , PRIMES is in P, URL: http://www.cse.iitk.ac.in/users/manindra/primalityv6.pdf, 2005.08.11 | MR 2123939
[5] - , Elliptic curves and primality proving, Mathematics of Computation, 61 (1993), 29-68. | MR 1199989 | Zbl 0792.11056
[6] , Detecting perfect powers in essentially linear time, Mathematics of Computation, 67 (1998), 1253-1283. | MR 1464141 | Zbl 0910.11057
[7] , Proving primality after Agrawal-Kayal-Saxena, URL: http://cr.yp.to/papers.html#aks, 2003.01.25
[8] , 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. | Zbl 1144.11085
[9] , 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] , Sharpening Primes is in P for a large family of numbers, Mathematics of Computation, 74 (2005), 2043-2059. | MR 2164112 | Zbl 1071.11071
[11] - , 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] , 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. | MR 2093202 | Zbl 1122.68456
[14] , Apology for the Proof of the Riemann Hypothesis, 2006.04.25, http://www.math.purdue.edu/branges/apology.pdf
[15] , A proof of the Riemann Hypothesis I, 2005.12.29, http://www.math.purdue.edu/branges/riemannzeta.pdf
[16] , A proof of the Riemann Hypothesis II, 2006.01.11, http://www.math.purdue.edu/branges/riemannII.pdf
[17] , Théorème de Brun-Tichmarsh; application au théorème de Fermat, Invent. Math., 79 (1985), 383-407. | MR 778134
[18] - , 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] - , Primality Testing using Elliptic Curves, Journal of the ACM, 46 (1999), 450-472. | MR 1812127 | Zbl 1064.11503
[20] - , Toward a deterministic polynomial time primality tests, URL: http://www.cse.iitk.ac.in/research/btp2002/primality.html, 2002
[21] - , Introduzione alla Crittografia, Hoepli Editore, Milano, 2004.
[22] - - (organizers), Future directions in algorithmic number theory, Workshop, March 24-28, 2003, Palo Alto, California, http://www.aimath.org/ARCC/workshops/primesinp.html
[23] - , Primality testing with Gaussian Periods, preliminary version, July 2005, URL: http://www.math.dartmouth.edu/carlp/PDF/complexity072805.pdf
[24] , 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] , 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 | Zbl 1127.11084
[26] , On the combined Fermat/Lucas probable prime test, in Crypto and Coding '99, Lecture Notes in Computer Science1746, Springer-Verlag1999 | MR 1861844
[27] , On Chebyshev-type inequalities for primes, The American Mathematical Monthly, 89 (1982), 126-129. | MR 643279 | Zbl 0494.10004
[28] - , Primality testing, Thesis, April 2001, URL: http://www.cse.iitk.ac.in/research/btp2001/primality.ps.gz, 2001
[29] , Every prime has a succinct certificate, SIAM Journal on Computing, 4 (1975), 214-220. | MR 391574 | Zbl 0316.68031
[30] , An Efficient Implementation of the AKS Polynomial-Time Primality Proving Algorithm, SCS Undergraduate Thesis (Advisor: Klaus Sutner), Carnegie Mellon, May 2005.
[31] , Elliptic curves over finite fields and the computation of square roots mod p, Math. Computation, 44 (1985), 483-494. | MR 777280 | Zbl 0579.14025
[32] , Introduzione alla complessità computazionale, URL:http://www.dimi.uniud.it/serafini/complcomp.pdf