Dado que tenemos una manera eficiente de descomponer en factores un número, ¿cómo podemos encontrar eficientemente el orden de algún módulo entero, otro entero coprimo N?

Puede comenzar por encontrar la factorización de N para poder calcular [math] \ phi (N) [/ math] (función totient de Euler), que da el orden del grupo multiplicativo en números enteros coprime a N módulo N.

Ahora supongamos que queremos calcular [matemáticas] ord (x) [/ matemáticas]. Como el orden de un elemento siempre divide el orden del grupo, tenemos que [math] \ phi (N) [/ math] es un múltiplo de ord (x). También sabemos que [math] x ^ m = 1 [/ math] iff m es un múltiplo de ord (x).

Por lo tanto, comenzamos con [matemáticas] m = \ phi (N) [/ matemáticas] para que [matemáticas] x ^ m = 1 [/ matemáticas]. Ahora, para cada factor primo de [math] \ phi (N) [/ math] intentamos dividirlo de m hasta que m ya no tenga ese factor primo o haría [math] x ^ m \ ne 1 [ /matemáticas].

Después de ese proceso, nos quedaremos con [math] ord (x) = m [/ math] ya que hemos eliminado el número máximo de cada factor primo posible de m.