Algoritmo AKS: differenze tra le versioni

Versione delle 19:39, 9 dic 2008

Versione delle 16:36, 21 feb 2009

Riga 1:

{{s|matematica}}

L''''algoritmo AKS''' (dalle iniziali dei tre ideatori, i matematici indiani Manindra Agrawal, Neeraj Kayal e

Nitin Saxena) è un [[test di primalità]] di [[P (complessità)|complessità polinomiale]]. In particolare, l'algoritmo ha tempo di esecuzione O(log^{12+εε} ''n''), mentre una variante proposta nel [[2005]] da [[Carl Pomerance]] e [[Hendrik Lenstra]] ha complessità O(log^{6+εε} ''n'')

Pubblicato nel [[2002]], ha fruttato ai suoi scopritori diversi premi, tra cui il [[premio Gödel]] e il [[premio Fulkerson]] nel [[2006]].

== Collegamenti esterni ==

* {{en}}[http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf L'articolo originale]

* [http://matematica.uni-bocconi.it/betti/AKS.htm Un articolo divulgativo sull'Algoritmo AKS]

{{Portale|Crittografia}}

[[Categoria:Test di primalità|AKS]]