Baby-Step Giant-Step
L'algorithme BSGS décompose le logarithme discret x=im+j (avec m=ceil(√n)) en deux étapes : précalculer g^j (pas de bébé), puis chercher h*(g^(-m))^i (pas de géant).
Objectif
Résoudre les logarithmes discrets avec un compromis temps-espace en complexité O(√n).
Mécanisme
Soit m=ceil(√n). Pas de bébé : calculer et stocker {g^j : 0≤j<m}. Pas de géant : pour i=0,1,... calculer h*g^(-im) et le chercher dans la table ; en cas de correspondance, x=im+j. Temps O(√n), espace O(√n).
Cas d’usage
- Résolution de logarithmes discrets
- Cryptanalyse
- Algorithmes de théorie des nombres