Algoritmo AKS: differenze tra le versioni

Naviga nella cronologia in modo interattivo

Contenuto cancellato Contenuto aggiunto

VisualeWikitesto

Versione delle 20:32, 20 ott 2008 modifica 87.4.60.211 (discussione) ←Nuova pagina: AKS(Agraval-Kayal-Saxena) Algoritmo per verificare la primalità di un intero con complessità polinomiale		Versione attuale delle 13:07, 21 feb 2016 modifica annulla Mat4free (discussione \| contributi) Utenti autoverificati 8 005 modifiche m Annullata la modifica 78991493 di Mat4free (discussione)
(25 versioni intermedie di 19 utenti non mostrate)
Riga 1: {{s\|teoria dei numeri}} ~~AKS(Agraval-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<sup>12+ε</sup> ''n''), mentre una variante proposta nel [[2005]] da [[Carl Pomerance]] e [[Hendrik Lenstra]] ha complessità O(log<sup>6+ε</sup> ''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]]