Fue diseñado por Manindra Agrawal, Neeraj Kayal y Nitin Saxena en el año 2002, su acrónimo es AKS. Es el primer algoritmo determinista en tiempo polinomial para prueba de números primos, su complejidad de tiempo de ejecución es O (log12+? n), donde ? > 0. A pesar de este avance teórico, el algoritmo no sirve para nada en la práctica, ni tampoco para el uso en aplicaciones criptográficas. En la universidad de Hyderabad, en India, realizaron un estudio de rendimiento de este algoritmo y trataron de obtener 10.000 números en el rango de 256 a 1.024 bits, en la identificación de un número compuesto tardaba de 30 a 60 minutos.
El algoritmo en la versión propuesta en 2004:
