Siguiente: Algoritmo de Adleman [1979] Un nivel arriba: En campos finitos Anterior: En campos finitos

Algoritmo de Silver (1978)

Los algoritmos siguientes son en campos finitos.

Dado un elemento $\alpha \in \mbox{\it GF}(p^n)^*$ y otro elemento $\beta$ que sea una potencia de $\alpha$ habrá que revisar una a una todas las potencias para encontrar el logaritmo discreto de $\beta$ en base $\alpha$.

El algoritmo de Silver, que presentamos a continuación reduce el número de posibilidades a revisar como potencias candidatas a ser el logaritmo, de hecho es idéntico al de Shank. El algoritmo aún sigue siendo bastante costoso e irrealizable cuando p y n son grandes. Este tiene una complejidad de $O(\sqrt{p^n-1})$ revisiones de igualdad de elementos en $\mbox{\it GF}(p^n)^*$.

Informalmente, el algoritmo se desempeña como sigue: Se forman dos listas, $\mbox{\it EltosConsec}$ y $\mbox{\it EltosBloque}$, de longitud $\sqrt{p^n-1}$ aproximadamente.

La primera contiene $\sqrt{p^n-1}$ potencias consecutivas de la base $\alpha$, corridas por el elemento cuyo logaritmo se quiere calcular, y la otra contiene $\sqrt{p^n-1}$ potencias de la base distribuídas uniformemente entre las pⁿ-1 posibles.

Un elemento en la intersección de las listas da el logaritmo discreto buscado.

En el recuadro 3.2 presentamos el algoritmo en un seudocódigo que se explica a sí mismo.

  

Figure 3.2: Algoritmo de Silver.

Siguiente: Algoritmo de Adleman [1979] Un nivel arriba: En campos finitos Anterior: En campos finitos