Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Logarithme discret
Résumé
Le logarithme discret est un objet mathématique utilisé en cryptologie. C'est l'analogue du logarithme réel qui est la réciproque de l'exponentielle, mais dans un groupe cyclique G fini.
Le logarithme discret est utilisé pour la cryptographie à clé publique, typiquement dans l'échange de clés Diffie-Hellman et le chiffrement El Gamal. La raison est que, pour un certain nombre de groupes, on ne connait pas d'algorithme efficace pour le calcul du logarithme discret, alors que celui de la réciproque, l'exponentiation, se réalise en un nombre de multiplications logarithmique en la taille de l'argument (voir exponentiation rapide),
On considère un groupe cyclique G fini d'ordre n (dont la loi est 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 certains entiers k ; de plus, deux quelconques de ces entiers sont nécessairement congrus modulo n. Le logarithme discret peut être défini comme le plus petit entier naturel k vérifiant cette propriété (il en existe un seul tel que 0 ≤ k < n). C'est donc une application réciproque de l'exponentiation k ↦ bk.
Considérons le groupe cyclique fini (Z7*, ×) et le générateur 3.
On a successivement 32 ≡ 2 mod 7, 33 ≡ 2×3 ≡ 6 mod 7, 34 ≡ 6×3 ≡ 4 mod 7. Dans Z7*, on a donc log3 4 = 4. De façon générale, dans ce groupe et pour le même générateur, le logarithme discret de x est le plus petit entier k tel que 3k ≡ x (mod 7).
Le logarithme discret peut aussi se définir comme la fonction logb de G dans Zn (où Zn désigne l'anneau des entiers modulo n) en associant à tout élément x de G la classe de congruence de k modulo n. Cette fonction est un isomorphisme de groupes, appelé logarithme discret de base b.
Par exemple, le logarithme discret en base 3 est une application du groupe cyclique fini (Z7*, ×) dans (Z6, +).
La formule 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, l'exponentiation discrète, ne l'est pas (grâce à l'algorithme d'exponentiation rapide) ; cette asymétrie est exploitée en cryptologie, pour la cryptographie à clé publique.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.