Paso de bebé, paso de gigante

Algoritmo para resolver el problema del logaritmo discreto

En la teoría de grupos , una rama de las matemáticas, el algoritmo baby-step giant-step es un algoritmo de encuentro en el medio para calcular el logaritmo discreto o el orden de un elemento en un grupo abeliano finito de Daniel Shanks . ^[1] El problema del logaritmo discreto es de importancia fundamental para el área de la criptografía de clave pública .

Muchos de los sistemas criptográficos más utilizados se basan en el supuesto de que el registro discreto es extremadamente difícil de calcular; cuanto más difícil sea, más seguridad proporciona a la transferencia de datos. Una forma de aumentar la dificultad del problema del registro discreto es basar el criptosistema en un grupo más grande.

Teoría

El algoritmo se basa en un equilibrio espacio-tiempo . Es una modificación bastante simple de la multiplicación por tanteo, el método ingenuo para hallar logaritmos discretos.

Dado un grupo cíclico de orden , un generador del grupo y un elemento del grupo , el problema es encontrar un entero tal que ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle x}$

${\displaystyle \alpha ^{x}=\beta \,.}$

El algoritmo de paso a paso se basa en reescribir : ${\displaystyle x}$

${\displaystyle x=im+j}$

${\displaystyle m=\left\lceil {\sqrt {n}}\right\rceil }$

${\displaystyle 0\leq i<m}$

${\displaystyle 0\leq j<m}$

Por lo tanto, tenemos:

${\displaystyle \alpha ^{x}=\beta \,}$

${\displaystyle \alpha ^{im+j}=\beta \,}$

${\displaystyle \alpha ^{j}=\beta \left(\alpha ^{-m}\right)^{i}\,}$

El algoritmo realiza un cálculo previo para varios valores de . Luego, fija un valor y prueba valores de en el lado derecho de la congruencia anterior, a la manera de una multiplicación de prueba. Prueba si la congruencia se cumple para cualquier valor de , utilizando los valores precalculados de . ${\displaystyle \alpha ^{j}}$ ${\displaystyle j}$ ${\displaystyle m}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \alpha ^{j}}$

El algoritmo

Entrada : Un grupo cíclico G de orden n , que tiene un generador α y un elemento β .

Salida : Un valor x que satisface . ${\displaystyle \alpha ^{x}=\beta }$

1. m ← Techo( √ n )
2. Para todo j donde 0 ≤ j < m :
   1. Calcular α ^j y almacenar el par ( j , α ^j ) en una tabla. (Ver § En la práctica)
3. Calcular α ^{− m} .
4. γ ← β . (establecer γ = β )
5. Para todo i donde 0 ≤ i < m :
   1. Verifique si γ es el segundo componente ( α ^j ) de cualquier par en la tabla.
   2. Si es así, devuelve im + j .
   3. Si no, γ ← γ • α ^{− m} .

En la práctica

La mejor manera de acelerar el algoritmo de pasos pequeños y pasos grandes es usar un esquema de búsqueda de tablas eficiente. Lo mejor en este caso es una tabla hash . El hash se realiza en el segundo componente y, para realizar la comprobación en el paso 1 del bucle principal, se aplica el hash a γ y se comprueba la dirección de memoria resultante. Dado que las tablas hash pueden recuperar y agregar elementos en el tiempo (tiempo constante), esto no ralentiza el algoritmo de pasos pequeños y pasos grandes en general. ${\displaystyle O(1)}$

La complejidad espacial del algoritmo es , mientras que la complejidad temporal del algoritmo es . Este tiempo de ejecución es mejor que el tiempo de ejecución del cálculo ingenuo de fuerza bruta. ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n)}$

El algoritmo de paso a paso, paso a paso, podría ser utilizado por un espía para obtener la clave privada generada en el intercambio de claves Diffie Hellman , cuando el módulo es un número primo que no es demasiado grande. Si el módulo no es primo, el algoritmo Pohlig–Hellman tiene una complejidad algorítmica menor y potencialmente resuelve el mismo problema. ^[2]

Notas

• El algoritmo de pasos pequeños y pasos gigantes es un algoritmo genérico que funciona para cualquier grupo cíclico finito.
• No es necesario conocer de antemano el orden exacto del grupo G. El algoritmo sigue funcionando si n es simplemente un límite superior del orden del grupo.
• Generalmente, el algoritmo de pasos pequeños y pasos grandes se utiliza para grupos cuyo orden es primo. Si el orden del grupo es compuesto, el algoritmo de Pohlig-Hellman es más eficiente.
• El algoritmo requiere O ( m ) de memoria. Es posible utilizar menos memoria eligiendo un m más pequeño en el primer paso del algoritmo. Al hacerlo, aumenta el tiempo de ejecución, que entonces es O ( n / m ). Alternativamente, se puede utilizar el algoritmo rho de Pollard para logaritmos , que tiene aproximadamente el mismo tiempo de ejecución que el algoritmo de pasos pequeños y pasos grandes, pero solo un pequeño requisito de memoria.
• Aunque este algoritmo se atribuye a Daniel Shanks, quien publicó el artículo de 1971 en el que aparece por primera vez, un artículo de 1994 de Nechaev ^{[3] afirma que} Gelfond lo conocía en 1962.
• Existen versiones optimizadas del algoritmo original, como el uso de las tablas de búsqueda truncadas sin colisiones de ^[4] o los mapas de negación y la inversión modular simultánea de Montgomery, como se propone en ^{[5] .}

Lectura adicional

• H. Cohen , Un curso de teoría de números algebraicos computacionales, Springer, 1996.
• D. Shanks , Número de clase, una teoría de factorización y géneros. En Proc. Symp. Pure Math. 20, páginas 415—440. AMS, Providence, RI, 1971.
• A. Stein y E. Teske, Métodos optimizados de pasos pequeños y pasos gigantes, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• AV Sutherland , Ordenar cálculos en grupos genéricos, tesis doctoral, MIT, 2007.
• DC Terr, Una modificación del algoritmo de pasos pequeños y grandes de Shanks, Mathematics of Computation 69 (2000), 767–773. doi :10.1090/S0025-5718-99-01141-2

Referencias

1. Daniel Shanks (1971), "Número de clase, una teoría de factorización y géneros", en Proc. Symp. Pure Math. , vol. 20, Providence, RI: American Mathematical Society, págs. 415–440
2. Maurer, Ueli M.; Wolf, Stefan (2000), "El protocolo Diffie-Hellman", Diseños, códigos y criptografía , 19 (2–3): 147–171, doi :10.1023/A:1008302122286, MR  1759615
3. VI Nechaev, Complejidad de un algoritmo determinado para el logaritmo discreto, Notas matemáticas, vol. 55, núm. 2 1994 (165-172)
4. Panagiotis Chatzigiannis, Konstantinos Chalkias y Valeria Nikolaenko (30 de junio de 2021). Descifrado homomórfico en cadenas de bloques mediante tablas de búsqueda de registros discretos comprimidos. Taller CBT 2021 (ESORICS) . Consultado el 7 de septiembre de 2021 .
5. Steven D. Galbraith, Ping Wang y Fangguo Zhang (10 de febrero de 2016). Cálculo de logaritmos discretos de curvas elípticas con un algoritmo mejorado de pasos pequeños y pasos gigantes. Avances en matemáticas de las comunicaciones . Consultado el 7 de septiembre de 2021 .

Enlaces externos

• Paso a paso: un ejemplo de código fuente en C