next up previous contents
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,xkj), $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 y0 cualquier elemento, sean j0 la posición en la que aparece y0 en L e i0 la posición en la que aparece y0 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 xkj0=y0=yx-i0 y por tanto y=xkj0+i0.

Guillermo Morales-Luna
2000-10-29