En teoría de grupos , el algoritmo de Pohlig-Hellman , a veces acreditado como el algoritmo Silver-Pohlig-Hellman , [1] es un algoritmo de propósito especial para calcular logaritmos discretos en un grupo abeliano finito cuyo orden es un entero suave .
El algoritmo fue introducido por Roland Silver, pero publicado por primera vez por Stephen Pohlig y Martin Hellman (independientes de Silver). [ cita requerida ]
Grupos de orden de potencias primarias
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 primaria . La idea básica de este algoritmo es calcular iterativamente el-dígitos ádicos del logaritmo "desplazando" repetidamente todos los dígitos desconocidos del exponente menos uno, y calculando ese dígito mediante métodos elementales.
(Tenga en cuenta que para facilitar la lectura, el algoritmo se establece para grupos cíclicos; en general, debe ser reemplazado por el subgrupo generado por , que siempre es cíclico.)
- Aporte. Un grupo cíclico de orden con generador y un elemento .
- Producción. El entero único tal que .
- Inicializar
- Calcular . Según el teorema de Lagrange , este elemento tiene orden.
- Para todos , hacer:
- Calcular . Por construcción, el orden de este elemento debe dividir, por eso .
- Usando el algoritmo de paso de bebé paso gigante , calcule tal que . Toma tiempo.
- Colocar .
- Regreso .
Asumiendo es mucho más pequeño que , el algoritmo calcula logaritmos discretos en la complejidad del tiempo , mucho mejor que el algoritmo de paso de bebé paso gigante .
El algoritmo general
En esta sección, presentamos el caso general del algoritmo de Pohlig-Hellman. Los ingredientes centrales son el algoritmo de la sección anterior (para calcular un módulo logarítmico de cada potencia prima en el orden de grupo) y el teorema del resto chino (para combinarlos con un logaritmo en el grupo completo).
(Nuevamente, asumimos que el grupo es cíclico, con el entendimiento de que un grupo no cíclico debe ser reemplazado por el subgrupo generado por el elemento base del logaritmo).
- Aporte. Un grupo cíclico de orden con generador , un elemento y una factorización prima .
- Producción. El entero único tal que .
- Para cada , hacer:
- Calcular . Según el teorema de Lagrange , este elemento tiene orden.
- Calcular . Por construcción,.
- Usando el algoritmo anterior en el grupo , calcular tal que .
- Resuelve la congruencia simultánea El teorema del resto chino garantiza que existe una solución única .
- Regreso .
- Para cada , hacer:
La exactitud de este algoritmo se puede verificar mediante la clasificación de grupos abelianos finitos : y al poder de puede entenderse como la proyección al grupo de factores de orden .
Complejidad
La entrada del peor de los casos para el algoritmo de Pohlig-Hellman es un grupo de primer orden: en ese caso, se degrada al algoritmo de paso de bebé paso gigante , por lo que la complejidad de tiempo del peor de los casos es. Sin embargo, es mucho más eficiente si el orden es fluido: específicamente, si es la factorización prima de , entonces la complejidad del algoritmo es
Notas
- ^ Mollin 2006 , pág. 344
- ^ Menezes, et. al 1997 , pág. 108
Referencias
- Mollin, Richard (18 de septiembre de 2006). Introducción a la criptografía (2ª ed.). Chapman y Hall / CRC. pag. 344 . ISBN 978-1-58488-618-1.
- S. Pohlig y M. Hellman (1978). "Un algoritmo mejorado para calcular logaritmos sobre GF (p) y su importancia criptográfica" (PDF) . Transacciones IEEE sobre teoría de la información (24): 106–110.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- Menezes, Alfred J .; van Oorschot, Paul C .; Vanstone, Scott A. (1997). "Problemas de referencia de teoría de números" (PDF) . Manual de criptografía aplicada . Prensa CRC . págs. 107–109 . ISBN 0-8493-8523-7.