Algoritmo AKS: differenze tra le versioni

Versione delle 17:46, 5 lug 2011

Versione delle 00:12, 21 nov 2011

Riga 1:

{{s|matematicateoria dei numeri}}

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'')