Logarithme discret
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de 
En algèbre générale et dans ses applications, le logarithme discret est défini en théorie des groupes par analogie avec le logarithme ordinaire.
On considère un groupe cyclique G d'ordre n (dont la loi sera notée multiplicativement) et un générateur b de G. Alors chaque élément x de G peut être écrit sous la forme x = bk pour un certain entier k ; de plus, deux quelconques de ces entiers sont nécessairement congrus modulo n. Il est ainsi possible de définir une fonction logb de G dans Zn (où Zn désigne l'anneau des entiers modulo n) en associant à tout élément x de Zn la classe de congruence de k modulo n. Cette fonction est un isomorphisme de groupe, appelé logarithme discret de base b.
La formule familière de changement de bases pour les logarithmes ordinaires reste valide : si c est un autre générateur de G, alors :
Pour certains groupes, le calcul des logarithmes discrets s'avère difficile, tandis que le problème inverse de l'exponentiation discrète ne l'est pas ; cette assymétrie est exploitée dans certaines applications en cryptologie.
Les choix populaires de G en cryptologie sont les groupes cycliques (Zp)× (constitués des nombres {1,...,p − 1} muni de la multiplication modulo le nombre premier p) ; voir le logarithme discret du cryptosystème d'ElGamal, l'échange de clés Diffie-Hellman et l'algorithme de signature numérique DSA.
Il est peut-être plus simple de comprendre les logarithmes discrets dans ce groupe avec un exemple :
Pour trouver la kieme puissance de l’un des nombres de ce groupe, ce qui se nomme exponentiation discrète, il faut élever ce nombre à la puissance k et calculer le reste de la division par p. Par exemple : 35 = 243. Le reste de la division entière de 243 par 7 étant 5, 35 dans le groupe (Z7)× est 5. Le logarithme discret est le problème inverse : étant donné 3k ≡ 5 (mod 7), quel est le plus petit k pour lequel cette proposition est vrai ?
L'algorithme de Pohlig-Hellman peut être utilisé pour calculer les logarithmes discrets dans ces groupes si p-1 est un produit de petits nombres premiers, ce qui oblige à l'éviter dans ce genre d'applications. Le calcul d'index est une autre méthode pour calculer les logarithmes discrets dans ces groupes, comme l'attaque anniversaire.
Des applications plus récentes de la cryptologie utilisent les logarithmes discrets dans les sous-groupes cycliques de courbes elliptiques sur les corps finis. Voir cryptologie sur les courbes elliptiques.
 |
Portail de la cryptologie – Accédez aux articles de Wikipédia concernant la cryptologie. |
