Algoritmo AKS
# Algoritmo AKS

L'algoritmo AKS (dalle iniziali dei tre ideatori, i matematici indiani Manindra Agrawal, Neeraj Kayal e Nitin Saxena) è un test di primalità di 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.

