Si no puede encontrarse tal a, entonces n es un número compuesto.
Este algoritmo es correcto ya que si a pasa el primer paso, podemos deducir que a y n son coprimos.
Si a también pasa el segundo paso, entonces el orden de a en el grupo (Z/nZ)* es igual a n − 1, lo que significa que el orden de ese grupo es n − 1, implicando que n es primo.
Recíprocamente, si n es primo, entonces existe una raíz primitiva módulo n y cualquier raíz primitiva pasará ambos pasos del algoritmo.
Para realizar estas potencias modulares debería usarse el método acelerado de exponenciación binaria.