Baby-step giant-step

Plantilla:Complicado En teoría de grupos, el algoritmo baby-step giant-step (también conocido como algoritmo de Shanks) 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 g^x=h.

1. Sea $m=\lceil \sqrt{(k-1)}\rceil$, donde $\lceil \rceil$ indica la función techo.
2. Calcular ${\alpha }_0=e_G,{\alpha }_1=g^m,{\alpha }_2=g^{2m},\dots ,{\alpha }_{m-1}=g^{(m-1)m}$. Armar y ordenar la lista $L=\{(1,0);({\alpha }_1,1),({\alpha }_2,2),({\alpha }_3,3),\dots \}$.
3. Calcular ${\beta }_0=h,{\beta }_1=h{g}^{-1},{\beta }_2=h(g^{-1}{)}^2,...$ hasta encontrar ${\beta }_i$ que sea igual a algún ${\alpha }_j$ de la lista L.
4. Si ${\beta }_i={\alpha }_j$ entonces la salida del algoritmo será $n=jm+i$.

Explicación

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

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

Ejemplo

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. $m=\lceil \sqrt{36}\rceil =6$,

2. Calculamos con esto:

${\alpha }_1=5^6\equiv 11(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)}$

${\alpha }_2=5^{12}\equiv 11\times 11\equiv 10(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)},$

${\alpha }_3=5^{18}\equiv 10\times 11\equiv 36(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)},$

${\alpha }_4=5^{24}\equiv 36\times 11\equiv 26(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)},$

${\alpha }_5=5^{30}\equiv 26\times 11\equiv 27(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)}$.

Armamos la lista: $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 ${\beta }_1=13\times 15\equiv 10(\mathrm{m}\mathrm{o}\mathrm{d}\mathrm{3}\mathrm{7}\mathrm{)}$, que coincide con ${\alpha }_2$.

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