Baby-step giant-step

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.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¿Por qué la respuesta dada por el algoritmo es correcta?, de donde se deduce quej m + i¿Por qué el algoritmo siempre da una respuesta?Dividimos n entre m y obtenemos n=qm+r, con(por definición del resto) yq m + r{\displaystyle \alpha _{q}=g^{qm}=g^{-r}h=\beta _{r}}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 ordenTomemos 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.O sea quem o d