O algoritmo de Agrawal-Kayal-Saxena, na prática, não é tão rápido assim. O que os indianos descobriram teoricamente é que o teste de primalidade está na classe P de problemas. Para uso prático, por exemplo, no algoritmo RSA de criptografia, ainda usa-se o algoritmo probabilístico de Rabin. Existe uma probabilidade pequena de que o algoritmo dê resposta errado, dizendo que um número é primo e, na realidade, não seja. Para diminuir o erro, aplica-se o algoritmo várias vezes ao mesmo número.