Utilizando algoritmos rápidos de exponenciación modular, se puede comprobar que el tiempo de ejecución de este algoritmo es O("k" × log"n" × log log "n" × log log log "n"), donde "k" representa el número de veces que se comprueba la congruencia para el número aleatorio "a" y "n" es el número a testear.