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 algoritmobaby-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.
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:
.
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. ISBN978-1-58488-508-5.
Datos:Q797983
Agosto 03, 2021
baby, step, giant, step, este, artículo, sección, tiene, estilo, difícil, entender, para, lectores, interesados, tema, puedes, favor, edítalo, contribuye, hacerlo, más, accesible, para, público, general, eliminar, detalles, técnicos, interesan, especialistas, . Este articulo o seccion tiene un estilo dificil de entender para los lectores interesados en el tema Si puedes por favor editalo y contribuye a hacerlo mas accesible para el publico general sin eliminar los detalles tecnicos que interesan a los especialistas En teoria de grupos el algoritmo baby step giant step tambien conocido como algoritmo de Shanks 1 es un metodo para calcular el logaritmo discreto de un elemento en un grupo Es un algoritmo generico es decir que funciona para cualquier grupo siempre que conozcamos el orden del mismo o una buena cota para el El problema del logaritmo discreto es de fundamental importancia para el area de la criptografia asimetrica Muchos de los sistemas criptograficos mas utilizados por ejemplo el cifrado ElGamal se basan en el supuesto de que el logaritmo discreto es extremadamente dificil de calcular Indice 1 El algoritmo 2 Explicacion 3 Ejemplo 4 ReferenciasEl algoritmo EditarSea un grupo G con orden k g un elemento de G h en el subgrupo generado por g La salida del algoritmo sera un x lt k tal que gx h Sea m k 1 displaystyle m left lceil sqrt k 1 right rceil donde displaystyle lceil rceil indica la funcion techo Calcular a 0 e G a 1 g m a 2 g 2 m a m 1 g m 1 m displaystyle alpha 0 e G alpha 1 g m alpha 2 g 2m ldots alpha m 1 g m 1 m Armar y ordenar la lista L 1 0 a 1 1 a 2 2 a 3 3 displaystyle L 1 0 alpha 1 1 alpha 2 2 alpha 3 3 ldots Calcular b 0 h b 1 h g 1 b 2 h g 1 2 displaystyle beta 0 h beta 1 hg 1 beta 2 h g 1 2 hasta encontrar b i displaystyle beta i que sea igual a algun a j displaystyle alpha j de la lista L Si b i a j displaystyle beta i alpha j entonces la salida del algoritmo sera n j m i displaystyle n jm i Explicacion Editar Por que la respuesta dada por el algoritmo es correcta Si b i a j displaystyle beta i alpha j significa que g j m h g i displaystyle g jm hg i de donde se deduce que g j m i h displaystyle g jm i h Por que el algoritmo siempre da una respuesta Sea h g n displaystyle h g n Dividimos n entre m y obtenemos n qm r con 0 r lt m displaystyle 0 leq r lt m por definicion del resto y 0 q lt m displaystyle 0 leq q lt m porque m 2 k gt n displaystyle m 2 geq k gt n O sea g q m r h displaystyle g qm r h de donde a q g q m g r h b r displaystyle alpha q g qm g r h beta r Este algoritmo mejora el metodo de fuerza bruta Mientras que este ultimo lleva un tiempo de orden O k el baby step giant step tiene un orden O k displaystyle O sqrt k Ejemplo EditarTomemos G como el grupo multiplicativo de los enteros modulo 37 Queremos hallar n tal que 5n 13 mod 37 Utilicemos el algoritmo de Shanks 1 m 36 6 displaystyle m lceil sqrt 36 rceil 6 2 Calculamos con esto a 1 5 6 11 m o d 37 displaystyle alpha 1 5 6 equiv 11 rm mod 37 a 2 5 12 11 11 10 m o d 37 displaystyle alpha 2 5 12 equiv 11 times 11 equiv 10 rm mod 37 a 3 5 18 10 11 36 m o d 37 displaystyle alpha 3 5 18 equiv 10 times 11 equiv 36 rm mod 37 a 4 5 24 36 11 26 m o d 37 displaystyle alpha 4 5 24 equiv 36 times 11 equiv 26 rm mod 37 a 5 5 30 26 11 27 m o d 37 displaystyle alpha 5 5 30 equiv 26 times 11 equiv 27 rm mod 37 Armamos la lista L 1 0 10 2 11 1 26 4 27 5 36 3 displaystyle L 1 0 10 2 11 1 26 4 27 5 36 3 3 La inversa de 5 modulo 37 es 15 O sea que b 1 13 15 10 m o d 37 displaystyle beta 1 13 times 15 equiv 10 rm mod 37 que coincide con a 2 displaystyle alpha 2 4 El n buscado es 2 6 1 13 displaystyle 2 times 6 1 13 Referencias Editar Stinson Douglas 2006 Shanks algorithm Cryptography theory and practice en ingles tercera edicion Chapman amp Hall CRC pp 236 238 ISBN 978 1 58488 508 5 Datos Q797983Obtenido de https es wikipedia org w index php title Baby step giant step amp oldid 132816595, wikipedia, wiki, leyendo, leer, libro, biblioteca,