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.
Referenze Bibliografiche
[1]
L. M. ADLEMAM -
M. A. HUANG,
Primality Testing and Abelian Varieties Over Finite Fields,
Lecture Notes in Mathematics,
1512,
Springer-Verlag 1992. |
fulltext (doi) |
MR 1176511[3]
M. AGRAVAL -
N. KAYAL -
N. SAXENA,
PRIMES is in P,
Annals of Mathematics,
160 (
2004), 781-793. |
fulltext (doi) |
MR 2123939[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 |
fulltext (doi) |
MR 2123939[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 1144.11085[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
[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
[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
[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.
[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 1127.11084[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 |
fulltext (doi) |
MR 1861844[28] P. PANDEY - R. BHATTACHARJEE, Primality testing, Thesis, April 2001, URL: http://www.cse.iitk.ac.in/research/btp2001/primality.ps.gz, 2001
[30] C. ROTELLA, An Efficient Implementation of the AKS Polynomial-Time Primality Proving Algorithm, SCS Undergraduate Thesis (Advisor: Klaus Sutner), Carnegie Mellon, May 2005.
[32] P. SERAFINI, Introduzione alla complessità computazionale, URL:http://www.dimi.uniud.it/serafini/complcomp.pdf
Con il contributo del Ministero per i Beni e le Attività Culturali