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/