Le problème computationnel consistant à trouver un exposant k dans un groupe multiplicatif fini G tel que g^k = h pour une base g donnée et un élément h ; c’est l’inversion de l’opération d’exponentiation dans ce groupe.

Principe

Exploiter la structure du groupe : algorithmes génériques (baby‑step giant‑step, Pollard rho) d’ordre racine carrée en complexité, et réductions dépendantes de la structure (Pohlig–Hellman, calcul des indices) lorsque l’ordre du groupe est factorisé ou de forme spéciale.

Démonstration

Exemple dans (Z/23Z)^× : g=5 et h=8. Calcul des puissances : 5^1=5, 5^2=2, 5^3=10, 5^4=4, 5^5=20, 5^6=8, donc k=6 et 5^6≡8 (mod 23).

Mauvaise application

Lancer des algorithmes de logarithme discret sans vérifier que g engendre le sous‑groupe concerné (un g non générateur n’assure pas k unique), ou appliquer l’index calculus dans des groupes où il est inefficace (par ex. certaines courbes elliptiques générales).

Conséquence

La difficulté ou la facilité computationnelle des logarithmes discrets fonde des primitives cryptographiques (échange de clés, signatures) et détermine les paramètres de sécurité ; des algorithmes efficaces brisent ces systèmes ou facilitent des calculs en théorie des nombres.

Inversion

L’exponentiation (calculer g^k) est l’opération facile en avant ; l’inverser (logarithme discret) est généralement beaucoup plus difficile, illustrant l’asymétrie entre opérations de groupe et leurs inverses en complexité calculatoire.

Limite

Défini pour des groupes multiplicatifs finis ou des sous‑groupes cycliques ; la complexité et les méthodes dépendent de l’ordre du groupe, de sa factorisation et de sa représentation (corps finis, courbes elliptiques) ; exclut les groupes continus et modèles additifs sans isomorphisme approprié.

Tension sémantique

Tension entre la difficulté générique (algorithmes de coût racine carrée) et la tractabilité dans des cas structurés (ordres lisses, index calculus) ; la sécurité pratique équilibre ces tendances contradictoires.

Synthèse

Le calcul du logarithme discret est l’inversion de l’exponentiation dans des groupes finis : un problème algorithmique dont la résolution dépend de la structure du groupe et qui mobilise une gamme d’algorithmes génériques et spécialisés aux complexités très différentes.