Baby-step giant-step

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme baby-step giant-step est, en théorie algorithmique des nombres et en théorie des groupes, une méthode de résolution du problème du logarithme discret dans un groupe cyclique quelconque qui a été introduite en 1971 par Daniel Shanks[1].

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, ou le protocole de Schnorr. C'est pourquoi pouvoir évaluer la difficulté de ce problème est une question importante en cryptographie.

Théorie[modifier | modifier le code]

Soit G un groupe cyclique de générateur d'ordre . Le problème de logarithme discret revient à chercher, pour dans G, un entier tel que :

L'algorithme baby-step giant-step est construit sur la division euclidienne de par . Ainsi , avec et et . Donc, on a:

Ainsi on passe d'un espace de recherche par force brute de , à avec cette méthode.

Algorithme[modifier | modifier le code]

Entrée: un groupe cyclique G d'ordre n, ayant un générateur α et un élément β.
Sortie: la valeur x satisfait .
m ← [√n]+1
Pour j tel que 0 ≤ j < m:    //Baby-Step
   Calculer αj et sauvegarder la paire (j, αj) dans une table de hachage. 
Calculer αm.
γ ← β. (Faire γ = β)
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.

Complexité[modifier | modifier le code]

L'algorithme requiert un espace en mémoire (pour le stockage de la table de hachage), et un temps [2].

D'autres méthodes comme l'algorithme ρ de Pollard avec l'algorithme de Floyd 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.

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Baby-step giant-step » (voir la liste des auteurs).

Annexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Bibliographie[modifier | modifier le code]

  • [Cohen 1996] (en) H. Cohen, A Course In Computational Algebraic Number Theory, Springer, coll. « GTM » (no 138), (ISBN 0-387-55640-0)
  • [Menezes, van Oorschot et Vanstone 1996] (en) Alfred J. Menezes, Paul C. van Oorschot et Scott A. Vanstone, Handbook of Applied Cryptography, (ISBN 0-8493-8523-7, lire en ligne [PDF]), « Chapitre 3.6 The discrete logarithm problem »
  • [Shanks 1971] (en) D. Shanks, « Class number, a theory of factorization and genera », Proc. Symp. Pure Math., vol. 20,‎ , p. 415-440
  • [Stein et Teske 2005] (en) A. Stein et E. Teske, « Optimized baby step-giant step methods », J. Ramanujan Math. Soc., vol. 1, no 20,‎ , p. 1-32
  • [Sutherland 2007] (en) A. V. Sutherland, Order computations in generic groups : PhD thesis, MIT, (lire en ligne [PDF])
  • [Terr 2000] (en) D. C. Terr, « A modification of Shanks’ baby-step giant-step algorithm », Mathematics of Computation, vol. 69,‎ , p. 767-773

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]