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  un groupe cyclique de générateur  d'ordre , dont la loi est noté multiplicativement. Le problème du logarithme discret revient à chercher, pour  dans , un entier  tel que .

La méthode naïve serait d'essayer successivement les entiers à partir de 0 jusqu'à trouver l'entier  solution, ce qui peut demander  essais dans le pire des cas, un temps exponentiel en la taille de .

Par division euclidienne par un entier ,  avec  et . On a alors que  si et seulement si 

L'algorithme baby-step giant-step utilise ceci pour un  bien choisi, le plus souvent   : pour trouver l'entier   on calcule la liste des   (les baby-steps), puis les   (les giant-steps) jusqu'à trouver un second membre déjà présent dans la liste des baby-steps, le couple  correspondant donne . 

En prenant , l'algorithme demande au pire 2⌈⌉ opérations de multiplications dans le groupe, contre  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 \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 ⌈⌉ é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).

Algorithme 

 Entrée: un groupe cyclique G d'ordre n, ayant un générateur 𝛼 et un élément 𝛽.
 Sortie: une valeur x vérifiant .
 m ← [√n]+1
 Pour j tel que 0 ≤ j < m:    //Baby-Step
    Calculer 𝛼j et sauvegarder la paire (j, 𝛼j), par exemple dans une table de hachage. 
 Calculer 𝛼−m (l'inverse de 𝛼m ou encore 𝛼n - m).
 𝛾 ← 𝛽. (Faire 𝛾 = 𝛽)
 Pour i tel que 0 ≤ i < m:   //Giant-Step
    Vérifier si 𝛾 est le second composant (𝛼j) d'une paire quelconque dans la table.
    Si oui, retourner im + j.
    Si non, 𝛾 ← 𝛾 • 𝛼−m.

Complexité 
L'algorithme requiert un espace  en mémoire (pour le stockage des baby-steps), et  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 , au prix d'une augmentation de la constante devant  en temps. En notation L, le crible algébrique réduit ce temps à , où , ce qui est sous-exponentiel en , 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  qui sera noté multiplicativement. Supposons que l'on connaisse une approximation du cardinal de , que l'on notera . Soit  un élément de  fixé. On recherche son ordre dans . Il s'agit alors de trouver le plus petit entier  non nul vérifiant . 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  (inclus) à  (exclus), dans l'ordre décroissant. On obtient l'algorithme suivant :

 Entrée: un groupe cyclique G d'ordre environ N, et un élément α
 Sortie: une valeur x vérifiant .
 m ← [√n]+1
 Pour j allant de m à 1:    //Baby-Step
    Calculer αj et sauvegarder la paire (j, αj), par exemple dans une table de hachage. 
 Calculer α−m.
 γ ← 1
 Pour i = 0 à (m − 1):   //Giant-Step
    Vérifier si γ est le second composant (αj) d'une paire quelconque dans la table.
    Si oui, retourner im + j.
    Si non, γ ← γ • α−m.

Notes et références

Annexes

Bibliographie

Article connexe 
Algorithme de Pohlig-Hellman

Lien externe 
Guénaël Renault,  .

Théorie des groupes
Théorie algorithmique des nombres