Logarithme discret
Le logarithme discret est une version du logarithme classique adaptée aux calculs effectués avec des entiers dans un corps ou un groupe fini. C’est un concept fondamental qui relie la théorie des nombres à la cryptographie moderne.
Concrètement, si \( G \) est un groupe cyclique d’ordre \( n \) et \( g \) un générateur de ce groupe, alors pour tout élément \( a \in G \), le logarithme discret \( x \) est l’entier qui vérifie :
\[ g^x \equiv a \mod n \]
où \( x \) appartient à l’intervalle \( [0, n-1] \).
Autrement dit, tout élément de \( G \) peut être écrit sous la forme \( g^k \) pour un certain entier \( k \). Le logarithme discret d’un élément \( a \) en base \( g \), noté logg(a), est donc l’exposant \( x \) qui satisfait \( g^x = a \) à l’intérieur du groupe.
Pourquoi est-ce important ? Le logarithme discret joue un rôle essentiel en théorie des nombres et en cryptographie. Son intérêt réside dans le fait qu’il est très difficile à inverser : il est simple de calculer \( g^x \mod n \), mais extrêmement ardu de retrouver \( x \) à partir du résultat. Cette dissymétrie fait du logarithme discret la base de nombreuses fonctions à sens unique, utilisées pour sécuriser les communications numériques, notamment dans les protocoles Diffie-Hellman ou ElGamal.
Exemple pratique
Pour mieux comprendre, prenons un exemple dans le corps fini \( \mathbb{Z}_{11} \), formé des entiers de 1 à 11, où les opérations se font modulo 11 :
$$ G = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11) $$
Dans ce système, \( 10 + 1 \equiv 11 \mod 11 \), mais \( 11 + 1 \equiv 1 \mod 11 \). En arithmétique modulaire, les valeurs « bouclent » de manière cyclique.
Voyons maintenant comment calculer des puissances dans ce groupe :
$$ 2^1 \mod 11 = 2 $$
$$ 2^2 \mod 11 = 4 $$
$$ 2^3 \mod 11 = 8 $$
$$ 2^4 \mod 11 = 5 $$
Remarque : En arithmétique ordinaire, \( 2^4 = 16 \). En arithmétique modulaire, on réduit le résultat : \( 16 \mod 11 = 5 \).
Nous voulons maintenant déterminer le logarithme discret de 9 en base 2, modulo 11, c’est-à-dire trouver \( x \) tel que :
$$ 2^x \equiv 9 \mod 11 $$
Essayons les valeurs possibles de \( x \) :
$$ 2^1 \mod 11 = 2 $$
$$ 2^2 \mod 11 = 4 $$
$$ 2^3 \mod 11 = 8 $$
$$ 2^4 \mod 11 = 5 $$
$$ 2^5 \mod 11 = 10 $$
$$ 2^6 \mod 11 = 9 $$
On obtient donc \( x = 6 \). Le logarithme discret de 9 en base 2 modulo 11 est 6.
Vérification : En arithmétique classique, \( 2^6 = 64 \). En réduisant modulo 11, on obtient \( 64 \mod 11 = 64 - 5 \times 11 = 9 \). On vérifie donc bien que : $$ 2^6 \mod 11 = 9 $$. En consultant la table de multiplication modulaire de ce groupe, on observe aussi que \( 8 \times 8 \equiv 9 \mod 11 \), ce qui confirme le résultat.
Cet exemple montre comment fonctionne concrètement le logarithme discret.
Il illustre aussi pourquoi, même si la vérification d’une relation comme \( 2^6 \equiv 9 \mod 11 \) est immédiate, retrouver l’exposant \( x \) devient un défi majeur lorsque les nombres utilisés sont très grands. C’est précisément cette difficulté de calcul qui rend le logarithme discret si précieux en cryptographie.
