Algoritmo AKS: differenze tra le versioni

Versione delle 20:33, 20 ott 2008

Versione attuale delle 13:07, 21 feb 2016

(24 versioni intermedie di 18 utenti non mostrate)

Riga 1:

{{s|teoria dei numeri}}

AKS(Agrawal-Kayal-Saxena)

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]].

Algoritmo per verificare la primalità di un intero con complessità polinomiale

== Collegamenti esterni ==

* {{cita web|http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf|L'articolo originale|lingua=en}}

* {{cita web|http://matematica.unibocconi.it/articoli/numeri-primi-e-complessit%C3%A0lalgoritmo-aks|Un articolo divulgativo sull'Algoritmo AKS}}

{{Portale|Crittografia|matematica}}

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