Baby-step giant-step

¿Por qué la respuesta dada por el algoritmo es correcta? Si ${\displaystyle \beta _{i}=\alpha _{j}}$ significa que ${\displaystyle g^{jm}=hg^{-i}}$, de donde se deduce que ${\displaystyle g^{jm+i}=h}$.

¿Por qué el algoritmo siempre da una respuesta? Sea ${\displaystyle h=g^{n}}$. Dividimos n entre m y obtenemos n=qm+r, con ${\displaystyle 0\leq r<m}$ (por definición del resto) y ${\displaystyle 0\leq q<m}$ (porque ${\displaystyle m^{2}\geq k>n}$). O sea: ${\displaystyle g^{qm+r}=h}$, de donde ${\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 orden ${\displaystyle O({\sqrt {k}})}$.

Tomemos G como el grupo multiplicativo de los enteros módulo 37. Queremos hallar n tal que 5ⁿ = 13 (mod 37). Utilicemos el algoritmo de Shanks.

1. ${\displaystyle m=\lceil {\sqrt {36}}\ \rceil =6}$,

2. Calculamos con esto:

${\displaystyle \alpha _{1}=5^{6}\equiv 11\ ({\rm {mod\ 37)}}}$

${\displaystyle \alpha _{2}=5^{12}\equiv 11\times 11\equiv 10\ ({\rm {mod\ 37),}}}$

${\displaystyle \alpha _{3}=5^{18}\equiv 10\times 11\equiv 36\ ({\rm {mod\ 37),}}}$

${\displaystyle \alpha _{4}=5^{24}\equiv 36\times 11\equiv 26\ ({\rm {mod\ 37),}}}$

${\displaystyle \alpha _{5}=5^{30}\equiv 26\times 11\equiv 27\ ({\rm {mod\ 37)}}}$.

Armamos la lista: ${\displaystyle L=\{(1,0),(10,2),(11,1),(26,4),(27,5),(36,3)\}}$.

3. La inversa de 5 módulo 37 es 15. O sea que ${\displaystyle \beta _{1}=13\times 15\equiv 10\ ({\rm {mod\ 37)}}}$, que coincide con ${\displaystyle \alpha _{2}}$.

4. El n buscado es ${\displaystyle 2\times 6+1=13}$.