Geodesic
Numeri primi: la certezza
Bollettino della Unione matematica italiana, Série 8, 10A (2007) no. 1, pp. 85-117.

Voir la notice de l'article provenant de la source Biblioteca Digitale Italiana di Matematica

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_a3,
     author = {Caire, Luisella and Cerruti, Umberto},
     title = {Numeri primi: la certezza},
     journal = {Bollettino della Unione matematica italiana},
     pages = {85--117},
     publisher = {mathdoc},
     volume = {Ser. 8, 10A},
     number = {1},
     year = {2007},
     zbl = {1277.11114},
     mrnumber = {2320482},
     language = {it},
     url = {http://geodesic.mathdoc.fr/item/BUMI_2007_8_10A_1_a3/}
}
TY  - JOUR
AU  - Caire, Luisella
AU  - Cerruti, Umberto
TI  - Numeri primi: la certezza
JO  - Bollettino della Unione matematica italiana
PY  - 2007
SP  - 85
EP  - 117
VL  - 10A
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/BUMI_2007_8_10A_1_a3/
LA  - it
ID  - BUMI_2007_8_10A_1_a3
ER  - 
%0 Journal Article
%A Caire, Luisella
%A Cerruti, Umberto
%T Numeri primi: la certezza
%J Bollettino della Unione matematica italiana
%D 2007
%P 85-117
%V 10A
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/BUMI_2007_8_10A_1_a3/
%G it
%F BUMI_2007_8_10A_1_a3
Caire, Luisella; Cerruti, Umberto. Numeri primi: la certezza. Bollettino della Unione matematica italiana, Série 8, 10A (2007) no. 1, pp. 85-117. http://geodesic.mathdoc.fr/item/BUMI_2007_8_10A_1_a3/

[1] L. M. Adlemam - M. A. Huang, Primality Testing and Abelian Varieties Over Finite Fields, Lecture Notes in Mathematics, 1512, Springer-Verlag 1992. | DOI | MR

[2] M. Agraval - N. Kayal - N. Saxena, PRIMES is in P, 2002. | DOI | MR

[3] M. Agraval - N. Kayal - N. Saxena, PRIMES is in P, Annals of Mathematics, 160 (2004), 781-793. | DOI | MR

[4] M. Agraval - N. Kayal - N. Saxena, PRIMES is in P, URL: http://www.cse.iitk.ac.in/users/manindra/primalityv6.pdf, 2005.08.11 | DOI | MR

[5] A.O.L. Atkin - F. Morain, Elliptic curves and primality proving, Mathematics of Computation, 61 (1993), 29-68. | DOI | MR | Zbl

[6] D. J. Bernstein, Detecting perfect powers in essentially linear time, Mathematics of Computation, 67 (1998), 1253-1283. | DOI | MR | Zbl

[7] D. J. Bernstein, Proving primality after Agrawal-Kayal-Saxena, URL: http://cr.yp.to/papers.html#aks, 2003.01.25

[8] D. J. Bernstein, 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

[9] D. J. Bernstein, 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] P. Berrizbeitia, Sharpening Primes is in P for a large family of numbers, Mathematics of Computation, 74 (2005), 2043-2059. | DOI | MR | Zbl

[11] L. Caire - U. Cerruti, 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. | fulltext bdim | fulltext EuDML

[12] U. Cerruti, 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-Verlag 2003. | DOI | MR | Zbl

[14] L. De Branges De Bourcia, Apology for the Proof of the Riemann Hypothesis, 2006.04.25, http://www.math.purdue.edu/branges/apology.pdf

[15] L. De Branges De Bourcia, A proof of the Riemann Hypothesis I, 2005.12.29, http://www.math.purdue.edu/branges/riemannzeta.pdf

[16] L. De Branges De Bourcia, A proof of the Riemann Hypothesis II, 2006.01.11, http://www.math.purdue.edu/branges/riemannII.pdf

[17] E. Fouvry, Théorème de Brun-Tichmarsh; application au théorème de Fermat, Invent. Math., 79 (1985), 383-407. | fulltext EuDML | DOI | MR

[18] S. Goldwasser - J. Kilian, 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] S. Goldwasser - J. Kilian, Primality Testing using Elliptic Curves, Journal of the ACM, 46 (1999), 450-472. | DOI | MR | Zbl

[20] N. Kayal - N. Saxena, Toward a deterministic polynomial time primality tests, URL: http://www.cse.iitk.ac.in/research/btp2002/primality.html, 2002

[21] A. Languisco - A. Zaccagnini, Introduzione alla Crittografia, Hoepli Editore, Milano, 2004.

[22] H. Lenstra - J. Pila - C. Pomerance (organizers), Future directions in algorithmic number theory, Workshop, March 24-28, 2003, Palo Alto, California, http://www.aimath.org/ARCC/workshops/primesinp.html

[23] H. W. Lenstra, Jr. - C. Pomerance, Primality testing with Gaussian Periods, preliminary version, July 2005, URL: http://www.math.dartmouth.edu/carlp/PDF/complexity072805.pdf

[24] F. Morain, 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] F. Morain, 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

[26] S. Müller, On the combined Fermat/Lucas probable prime test, in Crypto and Coding '99, Lecture Notes in Computer Science 1746, Springer-Verlag 1999 | DOI | MR

[27] M. Nair, On Chebyshev-type inequalities for primes, The American Mathematical Monthly, 89 (1982), 126-129. | DOI | MR | Zbl

[28] P. Pandey - R. Bhattacharjee, Primality testing, Thesis, April 2001, URL: http://www.cse.iitk.ac.in/research/btp2001/primality.ps.gz, 2001

[29] V. R. Pratt, Every prime has a succinct certificate, SIAM Journal on Computing, 4 (1975), 214-220. | DOI | MR | Zbl

[30] C. Rotella, An Efficient Implementation of the AKS Polynomial-Time Primality Proving Algorithm, SCS Undergraduate Thesis (Advisor: Klaus Sutner), Carnegie Mellon, May 2005.

[31] R. Schoof, Elliptic curves over finite fields and the computation of square roots mod p, Math. Computation, 44 (1985), 483-494. | DOI | MR | Zbl

[32] P. Serafini, Introduzione alla complessità computazionale, URL:http://www.dimi.uniud.it/serafini/complcomp.pdf