# Baby-step giant-step

En théorie algorithmique des nombres et en théorie des groupes, l'algorithme baby-step giant-step permet de résoudre le problème du logarithme discret dans un groupe cyclique quelconque. Il est dû à Daniel Shanks en 1971. C'est essentiellement un compromis temps-mémoire à partir de l'algorithme naïf par recherche exhaustive.
La difficulté du problème du logarithme discret est une hypothèse calculatoire sur laquelle reposent (plus ou moins directement) plusieurs schémas cryptographiques à clef publique, comme le chiffrement El Gamal, l'échange de clés Diffie-Hellman ou le protocole de Schnorr. C'est pourquoi pouvoir évaluer la difficulté de ce problème est une question importante en cryptographie.

## Théorie

Soit G un groupe cyclique de générateur α d'ordre n, dont la loi est noté multiplicativement. Le problème du logarithme discret revient à chercher, pour β dans G, un entier x tel que α$^x$ = β.
La méthode naïve serait d'essayer successivement les entiers à partir de 0 jusqu'à trouver l'entier x solution, ce qui peut demander n essais dans le pire des cas, un temps exponentiel en la taille de n.
Par division euclidienne par un entier m, $x=im+j$ avec 0 ≤ j < m et 0 ≤ i ≤ n/m. On a alors que α$^x$ = β si et seulement si α$^j$ = β(α$^{–m}$)$^i$
L'algorithme baby-step giant-step utilise ceci pour un m bien choisi, le plus souvent m=⌈√n⌉ : pour trouver l'entier x on calcule la liste des (j, α$^j$) (les baby-steps), puis les (i, β(α$^{-m}$)$^i$) (les giant-steps) jusqu'à trouver un second membre déjà présent dans la liste des baby-steps, le couple (i,j) correspondant donne x.
En prenant m = ⌈√n⌉, l'algorithme demande au pire 2⌈√n⌉ opérations de multiplications dans le groupe, contre n par recherche exhaustive, auquel il faut ajouter le temps nécessaire pour écrire la liste et chercher un élément commun, sous une forme qui permet d'optimiser cette recherche, sachant qu'une opération de comparaison de deux éléments du groupe est de toute façon beaucoup moins coûteuse a priori qu'une multiplication. Une possibilité est d'utiliser un tableau trié sur le second membre pour la première liste, et de procéder par dichotomie pour la recherche dans celui-ci, on a alors ${\ce {{\mathcal {O}}({\sqrt {n}}\log(n))}}$ opérations de comparaison, une autre solution est d'utiliser une table de hachage.
L'algorithme demande par contre de stocker ⌈√n⌉ éléments du groupe ce qui peut s'avérer à son tour rédhibitoire pour des groupes de taille importante (typiquement ceux utilisés en cryptographie).

## Complexité

L'algorithme requiert un espace ${\mathcal {O}}({\sqrt {n}})$ en mémoire (pour le stockage des baby-steps), et ${\mathcal {O}}({\sqrt {n}})$ en temps (une opération par itération des boucles).
D'autres méthodes comme l'algorithme ρ de Pollard (avec l'algorithme de Floyd pour la détection de cycle) peuvent réduire la consommation mémoire à un ${\mathcal {O}}(1)$, au prix d'une augmentation de la constante devant ${\sqrt {n}}$ en temps. En notation L, le crible algébrique réduit ce temps à $L\left({\tfrac {1}{3}},c\right)=\exp((c+o(1))\cdot (\log n)^{1/3}\cdot (\log \log n)^{1-1/3})$, où $c={\sqrt[{3}]{\tfrac {64}{9}}}\approx 1{,}923\ldots$, ce qui est sous-exponentiel en $\log n$, mais est limité aux sous-groupes multiplicatifs des corps finis. Ce qui rend l'algorithme inutilisable sur les groupes issus de courbes elliptiques, alors que l'algorithme baby-step giant-step reste applicable dans ce cas.

## Un exemple d'utilisation : calcul d'ordre

Le calcul de l'ordre d'un point dans un groupe de cardinal inconnu peut être nécessaire dans de nombreuses situations, comme notamment en cryptographie. L'algorithme Baby-Steps, Giant-Steps peut apporter une solution à ce problème.
Considérons un groupe $G$ qui sera noté multiplicativement. Supposons que l'on connaisse une approximation du cardinal de $G$, que l'on notera $N$. Soit $a$ un élément de $G$ fixé. On recherche son ordre dans $G$. Il s'agit alors de trouver le plus petit entier $x$ non nul vérifiant $a^{x}=1$. Il s'agit donc d'un cas particulier de la résolution du logarithme discret.
On peut donc utiliser l'algorithme Baby-Steps, Giant-Steps, mais il est nécessaire de le modifier légèrement afin d'obtenir une solution qui soit d'une part non nulle et d'autre part minimale. Pour cela, il suffit de calculer les baby-steps de $m$ (inclus) à $0$ (exclus), dans l'ordre décroissant. On obtient l'algorithme suivant :