En la teoría computacional de números , el algoritmo de cálculo de índices es un algoritmo probabilístico para calcular logaritmos discretos . Dedicado al logaritmo discreto en dónde es un cálculo de índice primo que conduce a una familia de algoritmos adaptados a campos finitos y a algunas familias de curvas elípticas. El algoritmo recopila relaciones entre los logaritmos discretos de primos pequeños, las calcula mediante un procedimiento de álgebra lineal y finalmente expresa el logaritmo discreto deseado con respecto a los logaritmos discretos de primos pequeños.
Descripción
En términos generales, el problema del registro discreto nos pide que encontremos una x tal que, donde se dan g , h y el módulo n .
El algoritmo (descrito en detalle a continuación) se aplica al grupo donde q es primo. Requiere una base de factores como entrada. Esta base de factores generalmente se elige para que sea el número -1 y los primeros r primos comenzando con 2. Desde el punto de vista de la eficiencia, queremos que esta base de factores sea pequeña, pero para resolver el logaritmo discreto para un grupo grande requerimos que la base de factores sea (relativamente) grande. En implementaciones prácticas del algoritmo, esos objetivos en conflicto se ven comprometidos de una forma u otra.
El algoritmo se realiza en tres etapas. Las dos primeras etapas dependen únicamente del generador gy del módulo primo q , y hallan los logaritmos discretos de una base de factores de r primos pequeños. La tercera etapa encuentra el logaritmo discreto del número deseado h en términos de los logaritmos discretos de la base de factores.
La primera etapa consiste en buscar un conjunto de r relaciones linealmente independientes entre la base de factores y la potencia del generador g . Cada relación contribuye con una ecuación a un sistema de ecuaciones lineales en r incógnitas, es decir, los logaritmos discretos de los r primos en la base de factores. Esta etapa es vergonzosamente paralela y fácil de dividir entre muchas computadoras.
La segunda etapa resuelve el sistema de ecuaciones lineales para calcular los registros discretos de la base de factores. Un sistema de cientos de miles o millones de ecuaciones es un cálculo significativo que requiere grandes cantidades de memoria, y es no paralela vergonzosamente, por lo que un superordenador se utiliza normalmente. Esto se consideró un paso menor en comparación con los otros para cálculos de registros discretos más pequeños. Sin embargo, los registros de logaritmos discretos más grandes [1] [2] fueron posibles solo al cambiar el trabajo del álgebra lineal al tamiz (es decir, aumentando el número de ecuaciones y reduciendo el número de variables).
La tercera etapa busca una potencia s del generador g que, cuando se multiplica por el argumento h , puede factorizarse en términos de la base del factor g s h = (−1) f 0 2 f 1 3 f 2 ··· p r f r .
Finalmente, en una operación demasiado simple para ser llamada realmente una cuarta etapa, los resultados de la segunda y tercera etapas se pueden reorganizar mediante una simple manipulación algebraica para calcular el logaritmo discreto deseado x = f 0 log g (−1) + f 1 log g 2 + f 2 log g 3 + ··· + f r log g p r - s .
La primera y la tercera etapas son vergonzosamente paralelas y, de hecho, la tercera etapa no depende de los resultados de las dos primeras etapas, por lo que puede realizarse en paralelo con ellas.
La elección del tamaño de la base de factores r es crítica y los detalles son demasiado intrincados para explicarlos aquí. Cuanto mayor sea la base de factores, más fácil será encontrar relaciones en la etapa 1 y más fácil será completar la etapa 3, pero cuantas más relaciones necesite antes de poder pasar a la etapa 2, más difícil será la etapa 2. También es importante la disponibilidad relativa de computadoras adecuadas para los diferentes tipos de computación requeridos para las etapas 1 y 2.
Aplicaciones en otros grupos
La falta de la noción de elementos primos en el grupo de puntos en las curvas elípticas hace imposible encontrar una base de factores eficiente para ejecutar el método de cálculo de índices como se presenta aquí en estos grupos. Por lo tanto, este algoritmo es incapaz de resolver logaritmos discretos de manera eficiente en grupos de curvas elípticas. Sin embargo: Para tipos especiales de curvas (las llamadas curvas elípticas supersingulares ) existen algoritmos especializados para resolver el problema más rápido que con los métodos genéricos. Si bien el uso de estas curvas especiales se puede evitar fácilmente, en 2009 se demostró que para ciertos campos el problema del logaritmo discreto en el grupo de puntos en las curvas elípticas generales sobre estos campos se puede resolver más rápido que con métodos genéricos. De hecho, los algoritmos son adaptaciones del método de cálculo de índices. [3]
El algoritmo
Entrada: Generador de logaritmos discretos g , módulo q y argumento h . Factor base {−1,2,3,5,7,11, ..., p r }, de longitud r + 1.
Salida: x tal que g x ≡ h (mod q ).
- relaciones ← lista_vacia
- para k = 1, 2, ...
- Usando un algoritmo de factorización de enteros optimizado para números suaves , intente factorizar (Residuo euclidiano) usando la base de factores, es decir, encuentre es tal que
- Cada vez que se encuentra una factorización:
- Almacene k y el calculadoes como un vector (esto es una llamada relación)
- Si esta relación es linealmente independiente de las otras relaciones:
- Agréguelo a la lista de relaciones
- Si hay al menos relaciones r + 1, salir del ciclo
- Forme una matriz cuyas filas sean las relaciones
- Obtenga la forma escalonada reducida de la matriz
- El primer elemento de la última columna es el logaritmo discreto de -1 y el segundo elemento es el logaritmo discreto de 2 y así sucesivamente
- para s = 1, 2, ...
- Trate de factorizar sobre la base de factores
- Cuando se encuentra una factorización:
- Producción
Complejidad
Suponiendo una selección óptima de la base de factores, el tiempo de ejecución esperado (usando la notación L ) del algoritmo de cálculo de índices se puede establecer como.
Historia
La idea básica del algoritmo se debe a Western y Miller (1968), [4] que, en última instancia, se basa en ideas de Kraitchik (1922). [5] Las primeras implementaciones prácticas siguieron a la introducción en 1976 del criptosistema Diffie-Hellman, que se basa en el logaritmo discreto. La disertación de Merkle en la Universidad de Stanford (1979) fue acreditada por Pohlig (1977) y Hellman y Reyneri (1983), quienes también hicieron mejoras en la implementación. [6] [7] Adleman optimizó el algoritmo y lo presentó en la forma actual. [8]
La familia Index Calculus
El cálculo de índices inspiró una gran familia de algoritmos. En campos finitos con por alguna prima , los algoritmos de última generación son el tamiz de campo numérico para logaritmos discretos, , Cuándo es grande en comparación con , la función tamiz de campo ,y Joux, [9] por , Cuándo es pequeño comparado con y el tamiz de campo numérico en alto grado, por Cuándo está en el medio. El logaritmo discreto en algunas familias de curvas elípticas se puede resolver a tiempo por , pero el caso general sigue siendo exponencial.
enlaces externos
- Logaritmos discretos en campos finitos y su significado criptográfico , por Andrew Odlyzko
- Discrete Logarithm Problem , de Chris Studholme, incluido el artículo del 21 de junio de 2002 "The Discrete Log Problem".
- A. Menezes, P. van Oorschot, S. Vanstone (1997). Manual de criptografía aplicada . Prensa CRC . págs. 107–109 . ISBN 0-8493-8523-7.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
Notas
- ^ Thorsten Kleinjung, Claus Diem, Arlen K. Lenstra, Christine Priplata, Colin Stahlke, "Cálculo de un logaritmo discreto de campo principal de 768 bits" , IACR sprint, 2017
- ^ Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, "A kilobit hidden snfs discrete logarithm computation" , IACR spring, julio de 2016
- ^ Diem, C (2010). "Sobre el problema del logaritmo discreto en curvas elípticas". Compositio Mathematica .
- ^ Western y Miller (1968) Tablas de índices y raíces primitivas , Royal Society Mathematical Tables, vol 9, Cambridge University Press.
- ↑ M. Kraitchik, Théorie des nombres , Gauthier - Villards, 1922
- ^ Pohlig, S. Aspectos algebraicos y combinatorios de la criptografía . Tech. Rep. No. 6602-1, Stanford Electron. Labs., Stanford, California, octubre de 1977.
- ^ ME Hellman y JM Reyneri, Cálculo rápido de logaritmos discretos en GF (q), Avances en criptología - Actas de Crypto, 1983
- ^ L. Adleman, Un algoritmo subexponencial para el problema del logaritmo discreto con aplicaciones a la criptografía , en el vigésimo simposio anual sobre los fundamentos de la informática, 1979
- ^ A. Joux, Un nuevo algoritmo de cálculo de índices con complejidad en característica muy pequeña [1]