En la teoría de grupos , una rama de las matemáticas, el pequeño paso gigante es un algoritmo de encuentro en el medio para calcular el logaritmo discreto o el orden de un elemento en un grupo abeliano finito debido a Daniel Shanks . [1] El problema de los registros discretos 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 una 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 una compensación entre el espacio y el tiempo . Es una modificación bastante simple de la multiplicación de prueba, el método ingenuo de 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
El algoritmo de paso de bebé paso gigante se basa en la reescritura :
Por tanto, tenemos:
El algoritmo calcula previamente para varios valores de . Entonces arregla un y prueba los valores de en el lado derecho de la congruencia anterior, a la manera de la multiplicación de prueba. Prueba para ver si se satisface la congruencia para cualquier valor de, utilizando los valores precalculados de .
El algoritmo
Entrada : Un grupo cíclico G de orden n , que tiene un generador α y un elemento β .
Salida : un valor x satisfactorio.
- m ← Techo ( √ n )
- Para todo j donde 0 ≤ j < m :
- Calcule α j y almacene el par ( j , α j ) en una tabla. (Ver § En la práctica )
- Calcule α - m .
- γ ← β . (establecer γ = β )
- Para todo i donde 0 ≤ i < m :
- Verifique si γ es el segundo componente ( α j ) de cualquier par en la tabla.
- Si es así, devuelva im + j .
- Si no, γ ← γ • α - m .
En la práctica
La mejor manera de acelerar el algoritmo de pasos gigantes 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 un hash a γ y se verifica la dirección de memoria resultante. Dado que las tablas hash pueden recuperar y agregar elementos en tiempo (tiempo constante), esto no ralentiza el algoritmo general de paso de bebé paso de gigante.
El tiempo de ejecución del algoritmo y la complejidad del espacio es , mucho mejor que el tiempo de ejecución del cálculo ingenuo de fuerza bruta.
El algoritmo de pasos gigantes de Baby-step se utiliza a menudo para resolver la clave compartida en el intercambio de claves Diffie Hellman , cuando el módulo es un número primo. Si el módulo no es primo, el algoritmo de Pohlig-Hellman tiene una complejidad algorítmica menor y resuelve el mismo problema.
Notas
- El algoritmo de paso de bebé paso de gigante es un algoritmo genérico. Funciona para todos los grupos cíclicos finitos.
- No es necesario conocer el orden del grupo G de antemano. El algoritmo aún funciona si n es simplemente un límite superior en el orden del grupo.
- Por lo general, el algoritmo de paso de bebé paso de gigante se usa 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 memoria O ( m ). Es posible utilizar menos memoria eligiendo una m más pequeña en el primer paso del algoritmo. Si lo hace, aumenta el tiempo de ejecución, que luego es O ( n / m ). Alternativamente, se puede usar el algoritmo rho de Pollard para logaritmos , que tiene aproximadamente el mismo tiempo de ejecución que el algoritmo de paso de bebé paso gigante, pero solo un pequeño requisito de memoria.
- Si bien este algoritmo se le 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.
Otras lecturas
- H. Cohen , Un curso de teoría de números algebraica computacional, Springer, 1996.
- D. Shanks , Número de clase, una teoría de factorización y géneros. En Proc. Symp. Matemática pura. 20, páginas 415—440. AMS, Providence, RI, 1971.
- A. Stein y E. Teske, Métodos optimizados de paso de bebé paso a paso gigante, Revista de la Sociedad Matemática Ramanujan 20 (2005), no. 1, 1–32.
- AV Sutherland , Cálculos de pedidos en grupos genéricos , tesis doctoral, MIT, 2007.
- DC Terr, una modificación del algoritmo de pasos gigantes de pasos de bebé de Shanks, Mathematics of Computation 69 (2000), 767–773. doi : 10.1090 / S0025-5718-99-01141-2
Referencias
- ^ Daniel Shanks (1971), "Número de clase, una teoría de factorización y géneros", En Proc. Symp. Matemática pura. , Providence, RI: American Mathematical Society, 20 , págs. 415–440
- ^ VI Nechaev, Complejidad de un algoritmo determinado para el logaritmo discreto, Notas matemáticas, vol. 55, no. 2 1994 (165-172)