![](//upload.wikimedia.org/wikipedia/commons/thumb/5/53/Help_books.svg/40px-Help_books.svg.png) | Este artículo o sección tiene un estilo difícil de entender para los lectores interesados en el tema. Si puedes, por favor edítalo y contribuye a hacerlo más accesible para el público general, sin eliminar los detalles técnicos que interesan a los especialistas. |
En teoría de grupos, el algoritmo baby-step giant-step (también conocido como algoritmo de Shanks[1]) es un método para calcular el logaritmo discreto de un elemento en un grupo. Es un algoritmo genérico, es decir que funciona para cualquier grupo, siempre que conozcamos el orden del mismo (o una buena cota para él).
El problema del logaritmo discreto es de fundamental importancia para el área de la criptografía asimétrica . Muchos de los sistemas criptográficos más utilizados (por ejemplo el cifrado ElGamal) se basan en el supuesto de que el logaritmo discreto es extremadamente difícil de calcular.
El algoritmo
Sea un grupo G con orden k, g un elemento de G, h en el subgrupo generado por g. La salida del algoritmo será un x<k tal que gx=h.
- Sea
, donde
indica la función techo. - Calcular
. Armar y ordenar la lista
. - Calcular
hasta encontrar
que sea igual a algún
de la lista L. - Si
entonces la salida del algoritmo será
.
Explicación
¿Por qué la respuesta dada por el algoritmo es correcta? Si
significa que
, de donde se deduce que
.
¿Por qué el algoritmo siempre da una respuesta? Sea
. Dividimos n entre m y obtenemos n=qm+r, con
(por definición del resto) y
(porque
). O sea:
, de donde
.
Este algoritmo mejora el método de "fuerza bruta". Mientras que este último lleva un tiempo de orden O(k), el "baby-step giant-step" tiene un orden
.
Ejemplo
Tomemos G como el grupo multiplicativo de los enteros módulo 37. Queremos hallar n tal que 5n = 13 (mod 37). Utilicemos el algoritmo de Shanks.
1.
,
2. Calculamos con esto:
![{\displaystyle \alpha _{1}=5^{6}\equiv 11\ ({\rm {mod\ 37)}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/721fd59eef64ebc357f49d164d13e335c1cb475f)
![{\displaystyle \alpha _{2}=5^{12}\equiv 11\times 11\equiv 10\ ({\rm {mod\ 37),}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2858cc80ba3352e2bfbbe244a812089f2b1223b6)
![{\displaystyle \alpha _{3}=5^{18}\equiv 10\times 11\equiv 36\ ({\rm {mod\ 37),}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0badc2fbb28d1d331fc0809c1c1f823f14c75d80)
![{\displaystyle \alpha _{4}=5^{24}\equiv 36\times 11\equiv 26\ ({\rm {mod\ 37),}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9b0feb12d8bb36fb5915272855e4e4c76d6693c0)
. - Armamos la lista:
.
3. La inversa de 5 módulo 37 es 15. O sea que
, que coincide con
.
4. El n buscado es
.
Referencias
- ↑ Stinson, Douglas (2006). «Shanks' algorithm». Cryptography: theory and practice (en inglés) (tercera edición). Chapman & Hall/ CRC. pp. 236-238. ISBN 978-1-58488-508-5.
Control de autoridades | - Proyectos Wikimedia
Datos: Q797983 |
---|
Datos: Q797983