Logarithme discret

Infos
En algèbre générale et dans ses applications d'arithmétique modulaire, 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
Logarithme discret

En algèbre générale et dans ses applications d'arithmétique modulaire, 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 \log_b de G dans Z_n (où Z_n désigne l'anneau des entiers modulo n) en associant à tout élément x de Z_n 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 : :\log_c (x) = \log_c(b) \cdot \log_b(x) 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 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 vraie ? 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. Catégorie:Théorie algorithmique des nombres Catégorie:Cryptologie Discret Catégorie:Théorie des groupes cs:Diskrétní logaritmus de:Diskreter Logarithmus en:Discrete logarithm es:Logaritmo discreto he:בעיית לוגריתם דיסקרטי it:Logaritmo discreto ko:이산 로그 pl:Logarytm dyskretny ru:Дискретное логарифмирование vi:Lôgarit rời rạc zh:离散对数
Sujets connexes
Algèbre générale   Anneau Z/nZ   Arithmétique modulaire   Congruence sur les entiers   Corps fini   Courbe elliptique   Cryptologie   Cryptosystème de ElGamal   Digital Signature Algorithm   Groupe (mathématiques)   Logarithme   Modulo   Nombre premier  
#
Accident de Beaune   Amélie Mauresmo   Anisocytose   C3H6O   CA Paris   Carole Richert   Catherinettes   Chaleur massique   Championnat de Tunisie de football D2   Classement mondial des entreprises leader par secteur   Col du Bonhomme (Vosges)   De viris illustribus (Lhomond)   Dolcett   EGP  
^