Paso de bebé, paso de gigante

Algoritmo para resolver el problema de logaritmo discreto.

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

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

Teoría

El algoritmo se basa en una compensación espacio-tiempo . Es una modificación bastante simple de la multiplicación de prueba, el método ingenuo para encontrar logaritmos discretos.

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

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

El algoritmo del paso gigante del bebé se basa en la reescritura : ${\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 tanto, tenemos:

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

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

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

El algoritmo precalcula varios valores de . Luego fija an y prueba valores de en el lado derecho de la congruencia anterior, a la manera de una multiplicación de prueba. Prueba para ver si se cumple la congruencia 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 satisfactorio . ${\displaystyle \alpha ^{x}=\beta }$

1. metro ← Techo( √ norte )
2. Para todo j donde 0 ≤ j < m :
   1. Calcule α ^j y almacene el par ( j , α ^j ) en una tabla. (Ver § En la práctica)
3. Calcule α ^{− m} .
4. γ ← β . (conjunto γ = β )
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 paso gigante es utilizar 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 verificación en el paso 1 del bucle principal, se aplica el hash a γ y se verifica 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 general de paso gigante. ${\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 ingenuo cálculo de fuerza bruta. ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O({\sqrt {n}})}$ ${\displaystyle O(n)}$

Un espía podría utilizar el algoritmo Baby-step de paso gigante para derivar la clave privada generada en el intercambio de claves Diffie Hellman ^{[ cita necesaria ]} , cuando el módulo es un número primo que no es demasiado grande. Si el módulo no es primo, el algoritmo de Pohlig-Hellman tiene una complejidad algorítmica menor y potencialmente resuelve el mismo problema.

Notas

• El algoritmo de paso de bebé y paso de gigante es un algoritmo genérico. Funciona para cada grupo cíclico finito.
• No es necesario conocer de antemano el orden exacto del grupo G. El algoritmo todavía funciona si n es simplemente un límite superior en el orden del grupo.
• Por lo general, el algoritmo de paso gigante se utiliza para grupos cuyo orden es primo. Si el orden del grupo es compuesto entonces el algoritmo de Pohlig-Hellman es más eficiente.
• El algoritmo requiere memoria O ( m ). Es posible utilizar menos memoria eligiendo una m más pequeña en el primer paso del algoritmo. Al hacerlo, aumenta el tiempo de ejecución, que luego 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 paso gigante, pero solo un pequeño requisito de memoria.
• Si bien 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 ^{[2] afirma que} Gelfond lo conocía en 1962.
• Existen versiones optimizadas del algoritmo original, como el uso de tablas de búsqueda truncadas sin colisiones de ^[3] o mapas de negación y la inversión modular simultánea de Montgomery como se propone en ^{[4] .}

Otras lecturas

• H. Cohen , Un curso de teoría algebraica computacional de números, Springer, 1996.
• D. Shanks , Número de clase, teoría de la factorización y géneros. En Proc. Síntoma. Matemática pura. 20, páginas 415—440. AMS, Providencia, Rhode Island, 1971.
• A. Stein y E. Teske, Métodos optimizados de pasos de bebé y pasos de gigante, Journal of the Ramanujan Mathematical Society 20 (2005), no. 1, 1–32.
• AV Sutherland , Cálculos de orden en grupos genéricos, tesis doctoral, MIT, 2007.
• DC Terr, Una modificación del algoritmo de paso gigante 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. Síntoma. Matemática pura. , Providence, RI: Sociedad Matemática Estadounidense, vol. 20, págs. 415–440
2. VI Nechaev, Complejidad de un algoritmo determinado para el logaritmo discreto, Mathematical Notes, vol. 55, núm. 2 1994 (165-172)
3. Panagiotis Chatzigiannis, Konstantinos Chalkias y Valeria Nikolaenko (30 de junio de 2021). Descifrado homomórfico en blockchains mediante tablas de búsqueda de registros discretos comprimidos. Taller CBT 2021 (ESORICOS) . Consultado el 7 de septiembre de 2021 .
4. Steven D. Galbraith, Ping Wang y Fangguo Zhang (10 de febrero de 2016). Computación de logaritmos discretos de curva elíptica con un algoritmo de paso gigante mejorado. Avances en Matemáticas de las Comunicaciones . Consultado el 7 de septiembre de 2021 .

enlaces externos

• Bebé paso a paso gigante: ejemplo de código fuente en C