Algoritmo de cálculo de índices

En teoría de números computacionales , el algoritmo de cálculo de índices es un algoritmo probabilístico para calcular logaritmos discretos . Dedicado al logaritmo discreto en donde es un 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 los 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 los primos pequeños. ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$ ${\displaystyle q}$

Descripción

En términos generales, el problema del logaritmo discreto nos pide encontrar una x tal que , donde g , h y el módulo n están dados. ${\displaystyle g^{x}\equiv h{\pmod {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 las implementaciones prácticas del algoritmo, esos objetivos conflictivos se ven comprometidos de una manera u otra. ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{*}}$

El algoritmo se ejecuta en tres etapas. Las dos primeras etapas dependen únicamente del generador g y del módulo primo q , y encuentran los logaritmos discretos de una base factorial 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 factorial.

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, es decir, los logaritmos discretos de los r primos en la base factorial. Esta etapa es vergonzosamente paralela y fácil de dividir entre muchos ordenadores.

La segunda etapa resuelve el sistema de ecuaciones lineales para calcular los logaritmos 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 no es vergonzosamente paralelo, por lo que generalmente se utiliza una supercomputadora . Esto se consideró un paso menor en comparación con los otros 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 al trasladar el trabajo del álgebra lineal al tamiz (es decir, aumentar el número de ecuaciones mientras se reduce el número de variables).

La tercera etapa busca una potencia s del generador g que, al multiplicarse por el argumento h , pueda factorizarse en términos de la base factorial 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 una simple manipulación algebraica 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 vergonzosamente 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 fundamental 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 se necesiten antes de poder pasar a la etapa 2, más difícil será esta última. La disponibilidad relativa de computadoras adecuadas para los diferentes tipos de cálculo necesarios para las etapas 1 y 2 también es importante.

Aplicaciones en otros grupos

La falta de la noción de elementos primos en el grupo de puntos de las curvas elípticas hace imposible encontrar una base de factores eficiente para ejecutar el método de cálculo de índices como el presentado 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 métodos genéricos. Si bien el uso de estas curvas especiales se puede evitar fácilmente, en 2009 se ha demostrado que para ciertos campos, el problema del logaritmo discreto en el grupo de puntos de las curvas elípticas generales sobre estos campos se puede resolver más rápido que con métodos genéricos. Los algoritmos son de hecho adaptaciones del método de cálculo de índices. ^[3]

El algoritmo

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

• relaciones ← lista_vacía
• para ${\displaystyle k=1,2,\ldots }$
  • Usando un algoritmo de factorización de números enteros optimizado para números suaves , intente factorizar (residuo euclidiano) usando la base del factor, es decir, encuentre s tal que ${\displaystyle g^{k}{\bmod {q}}}$ ${\displaystyle e_{i}}$ ${\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:
    • Almacene los valores calculados como un vector (esto se llama una relación) ${\displaystyle k}$ ${\displaystyle e_{i}}$ ${\displaystyle (e_{0},e_{1},e_{2},\ldots ,e_{r},k)}$
    • Si esta relación es linealmente independiente de las otras relaciones:
      • Agregarlo a la lista de relaciones
      • Si hay al menos relaciones, salir del bucle ${\displaystyle r+1}$
• Formar una matriz cuyas filas sean las relaciones
• Obtener la forma escalonada reducida de la matriz
  • El primer elemento de la última columna es el logaritmo discreto de y el segundo elemento es el logaritmo discreto de y así sucesivamente. ${\displaystyle -1}$ ${\displaystyle 2}$
• para ${\displaystyle s=1,2,\ldots }$
  • Intente factorizar sobre la base de factores ${\displaystyle g^{s}h{\bmod {q}}=(-1)^{f_{0}}2^{f_{1}}3^{f_{2}}\cdots p_{r}^{f_{r}}}$
  • 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.}$

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

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 la Universidad de Stanford de Merkle (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 la forma actual. ^[8]

La familia del cálculo indexado

El cálculo de índices inspiró una gran familia de algoritmos. En cuerpos finitos con para algún primo , los algoritmos de última generación son la Criba de Cuerpos Numéricos para Logaritmos Discretos, , cuando es grande en comparación con , ^[9] la criba de cuerpo de funciones , , ^[9] y Joux, ^[10] para , cuando es pequeño en comparación con y la Criba de Cuerpos Numéricos en Alto Grado, para cuando es de lado medio. El logaritmo discreto en algunas familias de curvas elípticas se puede resolver a tiempo para , pero el caso general sigue siendo exponencial. ${\displaystyle \mathbb {F} _{q}}$ ${\displaystyle q=p^{n}}$ ${\displaystyle p}$ ${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{64/9}}\,\right]}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\textstyle L_{q}\left[1/3,{\sqrt[{3}]{32/9}}\,\right]}$ ${\displaystyle L_{q}\left[1/4+\varepsilon ,c\right]}$ ${\displaystyle c>0}$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle L_{q}[1/3,c]}$ ${\displaystyle c>0}$ ${\displaystyle p}$ ${\displaystyle L_{q}\left[1/3,c\right]}$ ${\displaystyle c>0}$

Enlaces externos

• Logaritmos discretos en cuerpos finitos y su significado criptográfico, por Andrew Odlyzko
• Problema del logaritmo discreto, por Chris Studholme, incluido el artículo del 21 de junio de 2002 "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.

Notas

1. Thorsten Kleinjung, Claus Diem, Arlen K. Lenstra, Christine Priplata, Colin Stahlke, "Cálculo de un logaritmo discreto de campo primo de 768 bits", sprint IACR, 2017
2. Joshua Fried, Pierrick Gaudry, Nadia Heninger, Emmanuel Thome, "Un cálculo de logaritmo discreto de snfs oculto en kilobits", IACR primavera, julio de 2016
3. Diem, C (2010). "Sobre el problema del logaritmo discreto en curvas elípticas". Compositio Mathematica .
4. Western y Miller (1968) Tablas de índices y raíces primitivas , Royal Society Mathematical Tables, vol 9, Cambridge University Press.
5. M. Kraitchik, Théorie des nombres , Gauthier--Villards, 1922
6. Pohlig, S. Aspectos algebraicos y combinatorios de la criptografía . Tech. Rep. No. 6602-1, Stanford Electron. Labs., Stanford, California, octubre de 1977.
7. ME Hellman y JM Reyneri, Cálculo rápido de logaritmos discretos en GF (q), Avances en criptología – Actas de Crypto, 1983
8. L. Adleman, Un algoritmo subexponencial para el problema del logaritmo discreto con aplicaciones a la criptografía , en el 20º Simposio Anual sobre Fundamentos de la Ciencia de la Computación, 1979
9. Barbulescu, Razvan (2013). Algoritmos para logaritmos discretos en cuerpos finitos (PhD). Universidad de Lorena.
10. Joux, Antoine (agosto de 2013). Lange, Tanja ; Lauter, Kristin ; Lisoněk, Petr (eds.). Un nuevo algoritmo de cálculo de índices con complejidad L ( 1 / 4 + o ( 1 ) ) {\displaystyle L(1/4+o(1))} en característica muy pequeña. Selected Areas in Cryptography—SAC 2013. Lecture Notes in Computer Science. Vol. 8282. Burnaby, BC, Canadá: Springer. pp. 355–379. doi : 10.1007/978-3-662-43414-7_18 . ISBN 978-3-662-43414-7.