Es un método para calcular el logaritmo discreto de un número respecto a un módulo, conciendo una raíz primitiva $g$ de $m$ y el orden $ n $ de $g$ :
- calculamos la raíz cuadrada de $ n $ y tomamos el entero $m$ que resulta de redondear la raíz
- calculamos la lista $h,hg^{-1},hg^{-2},\ldots,hg^{-(m-1)}$
- calculamos la lista $1,g^m,g^{2m},\ldots,g^{(m-1)m}$
Si $h$ es una potencia de $g$, entonces $h=g^{i+jm}$ para algunos $i,j$ entre 0 y $m-1$ y los términos $hg^{-i}$ y $g^{jm}$ en las listas anteriores tienen que ser iguales.
Así que checando la igualdad en las listas se logra encontrar $h$
Ver también:
Logaritmo discreto
Ver también:
Orden de un entero (módulo m)
Ver también:
Raíces primitivas (módulo m)