Baby-step giant-step

Plantilla:Complicat En teoria de grups, l'algoritme baby-step giant-step (també conegut com a algoritme de Shanks) és un método per a calcular el logaritmo discret d'un element en un grup. És un algoritme genèric, és dir que funciona per a qualsevol grup, sempre que conegam l'orde del mateix (o una bona cota per a ell).

El problema del logaritmo discret és de fonamental importància per a l'àrea de la criptografia asimètrica . Molts dels sistemes criptográficos més utilisats (per eixemple el sifrat ElGamal) es basen suponent que el logaritmo discret és extremadament difícil de calcular.

L'algoritme

Siga un grup G en orde k, g un element de G, h en el subgrup generat per g. L'eixida de l'algoritme serà un x<k tal que g^x=h.

1. Siga $m=\lceil \sqrt{(k-1)}\rceil$, a on $\lceil \rceil$ indica la funció sostre.
2. Calcular ${\alpha }_0=e_G,{\alpha }_1=g^m,{\alpha }_2=g^{2m},\dots ,{\alpha }_{m-1}=g^{(m-1)m}$. Armar i ordenar la llista $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,\mathrm{...}$ fins a trobar ${\beta }_i$ que siga igual a algun ${\alpha }_j$ de la llista L.
4. Si ${\beta }_i={\alpha }_j$ llavors l'eixida de l'algoritme serà $n=jm+i$.

Explicació

¿Per qué la resposta donada per l'algoritme és correcta? Si ${\beta }_i={\alpha }_j$ significa que $g^{jm}=h{g}^{-i}$, d'a on es deduïx que $g^{jm+i}=h$.

¿Per qué l'algoritme sempre dona una resposta? Siga $h=g^n$. Dividim n entre m i obtenim n=qm+r, en $0\le r<m$ (per definició del restant) i $0\le q<m$ (perque $m^2\ge k>n$). O siga: $g^{qm+r}=h$, d'a on ${\alpha }_q=g^{qm}=g^{-r}h={\beta }_r$.

Este algoritme millora el método de "força bruta". Mentres que este últim du un temps d'orde O(k), el "baby-step giant-step" té un orde $O(\sqrt{k})$.