L'inverse modulaire

Diviser par 3, c'est multiplier par 1/3. En arithmétique modulaire, 1/3 n'existe pas — mais un substitut, oui.

La définition

L'inverse de a modulo n est l'entier x tel que :

a × x ≡ 1  (mod n)

Exemple : modulo 26, l'inverse de 3 est 9, car 3 × 9 = 27 ≡ 1 (mod 26).

Quand existe-t-il ?

Pas toujours ! C'est le point crucial :

a admet un inverse modulo n si et seulement si pgcd(a, n) = 1, c'est-à-dire si a et n sont premiers entre eux.

Modulo 26, le nombre 13 n'a pas d'inverse, car pgcd(13, 26) = 13. Quoi qu'on multiplie 13 par, on ne retombera jamais sur 1 modulo 26.

C'est pourquoi le chiffre affine y = ax + b (mod 26) impose que a soit premier avec 26 : sans inverse, le déchiffrement serait impossible et plusieurs lettres claires donneraient la même lettre chiffrée.

Le comprendre par l'exemple

Pourquoi pgcd = 1 est-il nécessaire ? Si a et n partagent un diviseur d > 1, alors tous les multiples de a modulo n sont aussi des multiples de d. Or 1 n'est pas multiple de d. On ne peut donc jamais atteindre 1.

À quoi ça sert

Dans RSA, la clé privée d est précisément l'inverse modulaire de la clé publique e. C'est cette relation qui fait que déchiffrer annule exactement chiffrer.

L'algorithme d'Euclide étendu calcule cet inverse rapidement, même pour des nombres de plusieurs centaines de chiffres.