Algoritmo de cálculo de índices

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${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$dónde${\displaystyle q}$Si es un número primo, el cálculo de índices conduce a una familia de algoritmos adaptados a cuerpos finitos y a algunas familias de curvas elípticas . El algoritmo recopila relaciones entre los logaritmos discretos de primos pequeños, los calcula mediante un procedimiento de álgebra lineal y, finalmente, expresa el logaritmo discreto deseado con respecto a los logaritmos discretos de primos pequeños.

En términos generales, el problema del logaritmo discreto nos pide encontrar un x tal que${\displaystyle g^{x}\equiv h{\pmod {n}}}$donde se dan g , h y el módulo n .

El algoritmo (que se describe en detalle a continuación) se aplica al grupo${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$donde q es primo. Requiere una base de factores como entrada. Esta base de factores suele elegirse como el número −1 y los primeros r primos, comenzando por 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, necesitamos que la base de factores sea (relativamente) grande. En las implementaciones prácticas del algoritmo, estos objetivos contradictorios se comprometen de una u otra forma.

El algoritmo se realiza en tres etapas. Las dos primeras dependen únicamente del generador g y del módulo primo q , y hallan los logaritmos discretos de una base de factores de r primos pequeños. La tercera etapa halla el logaritmo discreto del número deseado h en función 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 factorial y la potencia del generador g . Cada relación aporta una ecuación a un sistema de ecuaciones lineales con r incógnitas, concretamente los logaritmos discretos de los r números primos de la base factorial. Esta etapa es fácilmente paralelizable y se puede distribuir entre varios ordenadores.

La segunda etapa resuelve el sistema de ecuaciones lineales para calcular los logaritmos discretos de la base factorial. Un sistema de cientos de miles o millones de ecuaciones implica un cálculo significativo que requiere grandes cantidades de memoria y no es fácilmente paralelizable, por lo que normalmente se utiliza una supercomputadora . Esto se consideró un paso menor en comparación con los demás para cálculos de logaritmos discretos más pequeños. Sin embargo, los registros de logaritmos discretos más grandes ^{[ 1 ] [ 2 ]} solo fueron posibles trasladando el trabajo del álgebra lineal al método de cribado (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 ₀} 2 ^{f ₁} 3 ^{f ₂} ··· p _r ^{f _r} .

Finalmente, en una operación demasiado simple para ser realmente llamada una cuarta etapa, los resultados de la segunda y tercera etapas pueden reorganizarse mediante manipulación algebraica simple para calcular el logaritmo discreto deseado x = f ₀ log _g (−1) + f ₁ log _g 2 + f ₂ log _g 3 + ··· + f _r log _g p _r − s .

La primera y la tercera etapa son sorprendentemente paralelas, y de hecho la tercera etapa no depende de los resultados de las dos primeras, por lo que puede realizarse en paralelo con ellas.

La elección del tamaño de la base de factores r es crucial, y los detalles son demasiado complejos para explicarlos aquí. Cuanto mayor sea la base de factores, más fácil será encontrar relaciones en la etapa 1 y completar la etapa 3, pero se necesitarán más relaciones para pasar a la etapa 2, y esta última será más difícil. La disponibilidad relativa de ordenadores adecuados para los diferentes tipos de cálculos requeridos en las etapas 1 y 2 también es importante.

Entrada: Generador de logaritmos discretos${\displaystyle g}$, módulo${\displaystyle q}$y argumento${\displaystyle h}$. Base de factor${\displaystyle \{-1,2,3,5,7,11,\ldots ,p_{r}\}}$, de longitud${\displaystyle r+1}$. Producción:${\displaystyle x}$de tal manera que${\displaystyle g^{x}=h\mod q}$.

• relaciones ← lista_vacía
• para${\displaystyle k=1,2,\ldots }$
  • Utilizando un algoritmo de factorización de enteros optimizado para números suaves , intenta factorizar${\displaystyle g^{k}{\bmod {q}}}$(residuo euclidiano) usando la base del factor, es decir, encontrar${\displaystyle e_{i}}$es tal que${\displaystyle g^{k}{\bmod {q}}=(-1)^{e_{0}}2^{e_{1}}3^{e_{2}}\cdots p_{r}^{e_{r}}}$
  • Cada vez que se encuentra una factorización:
    • Almacenar${\displaystyle k}$y el calculado${\displaystyle e_{i}}$es como vector${\displaystyle (e_{0},e_{1},e_{2},\ldots,e_{r},k)}$(esto se llama una relación)
    • Si esta relación es linealmente independiente de las demás relaciones:
      • Añádelo a la lista de relaciones
      • Si hay al menos${\displaystyle r+1}$relaciones, bucle de salida
• Formar 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${\displaystyle -1}$y el segundo elemento es el logaritmo discreto de${\displaystyle 2}$etcétera
• para${\displaystyle s=1,2,\ldots }$
  • Intenta tener en cuenta${\displaystyle g^{s}h{\bmod {q}}=(-1)^{f_{0}}2^{f_{1}}3^{f_{2}}\cdots p_{r}^{f_{r}}}$sobre la base del factor
  • Cuando se encuentra una factorización:
    • Producción${\displaystyle x=f_{0}\log _{g}(-1)+f_{1}\log _{g}2+\cdots +f_{r}\log _{g}p_{r}-s.}$

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 expresar como ${\displaystyle L_{n}[1/2,{\sqrt {2}}+o(1)]}$.

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 tesis doctoral de Merkle en la Universidad de Stanford (1979) fue reconocida por Pohlig (1977) y Hellman y Reyneri (1983), quienes también realizaron mejoras a la implementación. ^{[ 6 ] [ 7 ]} Adleman optimizó el algoritmo y lo presentó en su forma actual. ^{[ 8 ]}

El cálculo de índices inspiró una gran familia de algoritmos. En campos finitos${\displaystyle \mathbb {F} _{q}}$con${\displaystyle q=p^{n}}$para algunos principiante${\displaystyle p}$, los algoritmos de última generación son el Number Field Sieve para logaritmos discretos,${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{64/9}}\,\right]}$, cuando${\displaystyle p}$es grande en comparación con${\displaystyle q}$, ^{[ 9 ]} el tamiz de campo de funciones ,${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{32/9}}\,\right]}$, ^{[ 9 ]} y Joux, ^{[ 10 ]}${\displaystyle L_{q}\left[1/4+\varepsilon ,c\right]}$para${\displaystyle c>0}$, cuando${\displaystyle p}$es pequeño en comparación con${\displaystyle q}$y el tamiz de campo numérico en alto grado,${\displaystyle L_{q}[1/3,c]}$para${\displaystyle c>0}$cuando${\displaystyle p}$es de lado medio. El logaritmo discreto en algunas familias de curvas elípticas se puede resolver en tiempo${\displaystyle L_{q}\left[1/3,c\right]}$para${\displaystyle c>0}$, pero el caso general sigue siendo exponencial.

• Logaritmos discretos en cuerpos finitos y su significado criptográfico , por Andrew Odlyzko
• Problema del logaritmo discreto , por Chris Studholme, incluyendo el artículo del 21 de junio de 2002 titulado "El problema del logaritmo discreto".
• A. Menezes; P. van Oorschot; S. Vanstone (1997). Manual de criptografía aplicada . CRC Press . págs. 107–109 . ISBN  0-8493-8523-7.