Algoritmo de Pohlig-Hellman

En la teoría de grupos , el algoritmo de Pohlig-Hellman , a veces acreditado como el algoritmo de Silver-Pohlig-Hellman , ^[1] es un algoritmo de propósito especial para calcular logaritmos discretos en un grupo abeliano finito cuyo orden es un número entero suave .

El algoritmo fue presentado por Roland Silver, pero publicado por primera vez por Stephen Pohlig y Martin Hellman (independiente de Silver). ^{[ cita requerida ]}

Como caso especial importante, que se utiliza como subrutina en el algoritmo general (ver más abajo), el algoritmo de Pohlig-Hellman se aplica a grupos cuyo orden es una potencia prima . La idea básica de este algoritmo es calcular iterativamente los dígitos -ádicos del logaritmo "desplazando" repetidamente todos los dígitos desconocidos menos uno en el exponente, y calculando ese dígito mediante métodos elementales.${\ estilo de visualización p}$

(Tenga en cuenta que para facilitar la lectura, el algoritmo se establece para grupos cíclicos; en general, debe reemplazarse por el subgrupo generado por , que siempre es cíclico).${\ estilo de visualización G}$${\displaystyle \langle g\rangle}$${\ estilo de visualización g}$

Suponiendo que es mucho más pequeño que , el algoritmo calcula logaritmos discretos en complejidad de tiempo , mucho mejor que el algoritmo de pasos gigantes de pasos pequeños .${\ estilo de visualización e}$${\ estilo de visualización p}$${\displaystyle O(e{\sqrt {p}})}$ ${\displaystyle O({\sqrt {p^{e}}})}$

En esta sección, presentamos el caso general del algoritmo de Pohlig-Hellman. Los ingredientes principales son el algoritmo de la sección anterior (para calcular un módulo de logaritmo para cada potencia prima en el orden del grupo) y el teorema chino del resto (para combinarlos en un logaritmo en el grupo completo).

Pasos del algoritmo de Pohlig-Hellman.