Le logarithme discret

13 octobre 2026
Discret ce logarithme, non ? 😉

Le logarithme discret n'est pas la fonction logarithme qui se planquerait, c'est simplement sa version non continue. Pourquoi est-elle intéressante ? Car elle est typique de la fonction facile à calculer dans un sens, mais pénible dans le sens inverse, une propriété que l'on aime en cryptographie.

Définition

Exponentielles et logarithmes

Une fonction exponentielle est une fonction "puissance de" ou "exposant", autrement dit c'est multiplier un nombre par lui-même un certain nombre de fois. Mais ces nombres sont "continus", ça peut être des nombres à virgule si vous préférez.

fonction exponentielle :     y = bx

b est appelée la base.


La fonction inverse, où on demande de calculer x étant donné y et la base b, est le logarithme dit de base b :

fonction logarithme :     x = logb (y)

Il existe une base particulière définissant ce qu'on appelle le logarithme naturel ou logarithme népérien, où la base b est un nombre particulier qui est le nombre d'Euler e dont le logarithme népérien vaut 1.

logarithme naturel : x = ln(y)    (la base est e)

avec

ln(1) = 0
ln(e) = 1

La dérivée du logarithme naturel est la fonction inverse 1/x
e vaut 2,71828...

Une propriété très intéressante est que le logarithme transforme une multiplication en addition. Mais il faut savoir calculer le logarithme d'un nombre dans les deux sens, c'est pour ça que dans le temps, il existait des tables de logarithmes.

Version discrète

Bon alors, cette version discrète, on peut la voir ?
Ou est-elle tellement effacée et modeste qu'elle en est invisible ? 😄
On dit « discret » parce que l'on va considérer les nombres entiers, qui sont tous séparés les uns des autres.
Par exemple, il n'y a rien entre 2 et 3.
🤔 Ah ! Ce n'est pas continu.
Exactement.
🧐 De plus, on l'applique à un groupe cyclique fini.
🥴 Un quoi ?
Un exemple sera plus parlant.
Les 7 chiffres 0,1,2,3,4,5,6 forment un tel groupe.
7 est premier, c'est voulu ?
Oui, pour diverses raisons.
Lorsque tu feras une addition ou une multiplication avec des nombres de ce groupe, tu vas tomber sur des nombres plus grands que 7
Immanquablement
On définit alors l'opération modulo, qui est simplement le reste de la division par 7.
Ah ! si je fais 6+2, j'obtiens 8, mais je reviens à 0 pour 7, puis j'ai 1 pour le 8
Oui. 6 + 2 = 1
Ça s'écrit 6 + 2 ≡ 1 mod 7
Ça marche aussi pour les multiplications ?
Bien sûr. Une multiplication n'est qu'une série d'additions
2 × 6 ≡ 5 mod 7
Je te vois venir. Une exponentielle n'est qu'une série de multiplications !
5³ = 5 × 5 × 5 ≡ 6 mod 7
😒 Et où est le problème ?
L'opération inverse, le logarithme discret, n'est pas facile à calculer.
Si je te donne la base 5, et le résultat 6, comment calculer la puissance ?
Il faut retrouver la valeur 3, c'est ça ?
Oui. Là, ça va encore parce qu'il s'agit de petits nombres, mais dès qu'on manipule des gros nombres, c'est très difficile.

Étant donné y, avec n premier, trouver l'exposant x plus petit que n, tel que :

bx ≡ y mod n

Ce calcul est généralement difficile. Mais apparemment pas assez pour faire reposer de la cryptographie uniquement là-dessus, la factorisation est autrement plus difficile.

Calculs

Exponentiation

Si le calcul d'une exponentielle discrète est assez évident ça ne sont que des multiplications après tout, il faut quand même ruser un peu quand les nombres deviennent grands. Voici 2 exemples :

6517 modulo 3233 = ?
27902753 modulo 3233 = ?

Le nombre 3233 sera, dans le domaine cryptographique, un nombre de 2048 bits, soit 617 chiffres décimaux. Oups !

😱 Aaaahhhh !
😕 Qu'est-ce qu'il t'arrive ?
😧 Déjà, calculer 65 à la puissance 17, ce n'est pas drôle
😬 mais alors 2790 à la puissance 2753, c'est carrément...
On connait une ruse, l'algorithme d'exponentiation rapide
J'espère que ton algorithme est efficace, sinon on n'est pas arrivé...

Exponentiation rapide

Calculer 27902753 modulo 3233

Il ne faut pas calculer 27902753, mais remarquer que :

27902753 modulo 3233 = [27902753-1 modulo 3233] * 2790

Autrement dit, il suffit de multiplier uniquement le reste, ce qui va éviter des nombres vraiment astronomiques.

Mais ce sera quand même assez long.

6517 modulo 3233 = 2790
27902753 modulo 3233 = 65

Logarithme discret

On peut toujours tenter un calcul exhaustif de tous les cas, mais ça risque d'être vraiment très très long. Pour donner un exemple en modulo 7, et la base 3 :

  • 3º mod 7 = 1
  • 3¹ mod 7 = 3
  • 3² mod 7 = 2
  • 3³ mod 7 = 6
  • ...

Quelques algorithmes ont été proposés (je vous laisse chercher), mais généralement c'est quand même assez long, mais on juge que ce n'est pas suffisamment long pour être cryptographiquement directement utilisable pour un niveau de sécurité comme celui du chiffrement RSA.

Usages

L'exponentiation sert beaucoup dans le chiffrement RSA, mais pas vraiment le logarithme discret seul, la sécurité ne repose pas dessus.


Si le logarithme discret seul parait insuffisant, il devient intéressant lorsqu'il est associé à une courbe elliptique, et c'est l'objet de recherches et d'applications dans le domaine cryptographique. C'est l'ECC pour Elliptic Curve Cryptography.

Encore de l'exponentiation, mais en plus compliqué avec un polynôme.
Certaines propriétés mathématiques sont intéressantes dans ce cas pour la crypto.

Les clés créées avec des courbes elliptiques sont nettement plus petites que celles utilisées en RSA, pour un niveau de sécurité équivalent, aussi elles sont intéressantes dès que l'on doit faire du chiffrement avec une puissance de calcul réduite (notamment en embarqué, pour les cartes à puce, celles des passeports).

Du coup on retrouve le logarithme discret dans le chiffrement pour le protocole Internet SSL et SSH avec un échange de clés Diffie-Hellman. Ainsi que pour le VPN, les messageries sécurisées et autres blockchains. Il faut se souvenir que si on arrivait à casser une clé (et ce serait long à faire), la communication de cet échange serait compromise, mais uniquement cet échange-là. Il faudrait recommencer pour un autre échange, aussi le jeu n'en vaut généralement pas la chandelle.


J'ai juste effleuré le sujet, histoire de savoir de quoi on parle. À vous de creuser si ça vous intéresse.

L'appellation logarithme discret m'a toujours fait sourire, probablement l'antagonisme entre une fonction bien mathématique, et une discrétion qui reste sur la réserve.