Algoritmo AKS
![Abbozzo](http://upload.wikimedia.org/wikipedia/commons/thumb/0/0e/Puzzle_stub.svg/45px-Puzzle_stub.svg.png)
Questa voce sull'argomento teoria dei numeri è solo un abbozzo.
Contribuisci a migliorarla secondo le convenzioni di Wikipedia.
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(log12+ε n), mentre una variante proposta nel 2005 da Carl Pomerance e Hendrik Lenstra ha complessità O(log6+ε 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) L'articolo originale (PDF), su cse.iitk.ac.in.
- Un articolo divulgativo sull'Algoritmo AKS, su matematica.unibocconi.it.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Ambox_padlock_green.svg/25px-Ambox_padlock_green.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/af/Crystal128-kmplot.svg/25px-Crystal128-kmplot.svg.png)