Table des matières
Inverse modulaire
Les techniques de chiffrement font usage des calculs avec modulo. Connaissant les nombres entiers $a > 1$ et $p > a$ premier, on a parfois besoin de trouver $u$ vérifiant $a \times u \mod p = 1$.
Rappel de ce qu'est modulo
Le modulo suit le principe des points d'une horloge. Prenons les points sur le cercle à droite. Nous avons 12 points sur le cercle, il s'agit donc d'un $\mod 12$.
L'idée est de compter les points dans le sens indiqué et si on dépasse 11, de continuer en boucle. À ce jeu, on réalisera que le nombre 53 tombera en face de 5.
$$53 = 4 \times 12 + 5 \Rightarrow 53\mod 12 = 5$$
5 est donc le reste de la division entière de 53 par 12 ce qui s'écrit en Python :
>>> 53 % 12 5
53 est donc au même endroit que 5 sur notre cercle. Le mathématicien, rigoureux, ne dira pas que 53 est égal à 5. Il dira que ces deux nombres sont équivalents d'un certain point de vue et il pourra l'écrire de cette façon $53 \equiv 5 \, [12]$ ou encore $53 \overset{12}{\equiv} 5$.
Algorithme d'Euclide étendu
On exploite des propriétés arithmétiques importantes. L'une d'elle est le théorème de Bézout qui nous dit :
Soient $a, b \in \mathbb{N}$, on peut trouver $u, v \in \mathbb{Z}$ tels que $a\cdot u + b\cdot v = PGCD(a,b)$.
Wikipedia nous donne l'algorithme d'Euclide étendu que je reproduis ici (presque) à l'identique :
ENTRÉES : a, b entiers (naturels)
SORTIES : r entier (naturel) et u, v entiers relatifs tels que r = pgcd(a, b) et r = a*u+b*v
r, u, v, r', u', v' = a, 1, 0, b, 0, 1
TANT QUE r' ≠ 0 FAIRE
q = r÷r'
r, u, v, r', u', v' = r', u', v', r - q *r', u - q*u', v - q*v'
FIN TANT QUE
RENVOYER r, u, v
Le symbole ÷ représente une division entière, c'est à dire // en Python.
L'algorithme d'Euclide normal est celui qui permet de calculer le PGCD. Cet algorithme est un peu plus complet puisqu'il donne en plus les valeurs de u et v.
Il y a une infinité de paires u,v. Cet algorithme nous renvoie donc une de ces paires. C'est justement celle dont nous avons besoin.
Application à notre cas
Nous voulons trouver $u$ entier tel que $a\cdot u \mod p = 1$, avec $0 \leqslant u < p$.
$p$ est premier, donc $PGCD(a,p) = 1$ donc nous cherchons $u$ tel que $a\cdot u \mod p = PGCD(a,p)$, ce qui revient à dire $a\cdot u + p\cdot v = PGCD(a,p)$ pour un certain entier $v$.
Cela correspond au théorème de Bézout et à l'algorithme d'Euclide étendu. La valeur de u renvoyée est justement celle que nous voulons.
À faire
Vous devez écrire en Python une fonction inverse_modulaire(a, p) qui reprend l'algorithme d'Euclide étendu en tenant compte des adaptations :
- Au lieu de
b, nous voulonsp, - Au lieu de renvoyer
(r, u, v), nous ne voulons queu
Pour vérifier :
# 6 * 9 = 54 donc 6 * 9 % 53 = 1 assert inverse_modulaire(6,53) == 9 # dans le même genre... assert inverse_modulaire(18,53) == 3 assert inverse_modulaire(51,53) == 26 assert inverse_modulaire(52,53) == 52 assert inverse_modulaire(1,53) == 1