Siguiente: Algoritmo de Pohlig-Hellman Un nivel arriba: En anillos de residuos Anterior: En anillos de residuos

Algoritmo de Shank

El Algoritmo de Shank resuelve el problema del logaritmo discreto en tiempo $O(\sqrt{p})$. En lo que sigue, todas las operaciones aritméticas son hechas en $Z\!\!\!Z_p$. Formemos la lista de $k=\left\lceil\sqrt{p-1}\right\rceil$ entradas $L=\left(x^{kj}\right)_{j=0}^{k-1}$, y sea L' la lista de parejas de la forma (j,x^kj), $j=0,\ldots,k$, ordenada respecto a su segunda componente. Formemos ahora la lista $M=\left(yx^{-i}\right)_{i=0}^{k-1}$, y sea M' la lista de parejas de la forma (i,yx^-i), $i=0,\ldots,k$, ordenada respecto a su segunda componente. Sea y₀ cualquier elemento, sean j₀ la posición en la que aparece y₀ en L e i₀ la posición en la que aparece y₀ en M. La localización de estos índices se hace con los arreglos L' y M'. El logaritmo discreto de y, respecto a x, es: $\log_x(y)=\left(kj_0+i_0\right)\mbox{\rm mod }(p-1)$. En efecto, se tiene x^kj₀=y₀=yx^-i₀ y por tanto y=x^kj₀+i₀.