Inverse modulaire

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques et plus précisément en arithmétique modulaire, l'inverse modulaire d'un entier a pour la multiplication modulo n est un entier u satisfaisant l'équation :

u\equiv a^{-1}\pmod n.

En d'autres termes, il s'agit de l'inverse dans l'anneau des entiers modulo n, noté ℤ/nℤ ou ℤn, ce qui est équivalent à :

au\equiv1\pmod n.

L'inverse de a modulo n existe si et seulement si a et n sont premiers entre eux, (c.-à-d. si PGCD(a, n) = 1). Si cet inverse existe, l'opération de division par a modulo n équivaut à la multiplication par son inverse.

Définition équivalente[modifier | modifier le code]

D'après la définition ci-dessus, u est un inverse de a modulo n s'il existe un entier v tel que

1-au=nv

ou encore : tel que

au+nv=1.

Existence et unicité[modifier | modifier le code]

Vu ce qui précède, a possède un inverse modulo n si et seulement s'il existe deux entiers u et v tels que au + nv = 1. D'après le théorème de Bachet-Bézout, ceci a lieu si et seulement si PGCD(a, n) = 1, c'est-à-dire si a et n sont premiers entre eux.

De plus, si un tel inverse existe alors il est unique (modulo n) et peut se calculer grâce à l'algorithme d'Euclide étendu ou au théorème d'Euler : cf. section « Méthodes de calcul » ci-dessous.

Exemple[modifier | modifier le code]

Supposons que l'on veuille chercher l'inverse modulaire u de 3 modulo 11.

u\equiv3^{-1}\pmod{11}.

Cela revient à calculer u vérifiant

3u\equiv1\pmod{11}.

Dans l'ensemble de ℤ11, une solution est 4 car

3\times4=12\equiv1\pmod{11},

et c'est la seule. Par conséquent, l'inverse de 3 modulo 11 est 4.

À partir du moment où l'on a trouvé l'inverse de 3 dans ℤ11, on peut trouver une infinité d'autres entiers u qui satisfont aussi cette congruence. Il suffit d'ajouter des multiples de n = 11 à l'inverse que nous avons trouvé. Autrement dit, les solutions sont

u=4+11k,\quad k\in\Z,

c'est-à-dire les éléments de {…, –18, –7, 4, 15, 26, …}.

Méthodes de calcul[modifier | modifier le code]

Algorithme d'Euclide étendu[modifier | modifier le code]

L'algorithme d'Euclide étendu permet génériquement de trouver des solutions à l'identité de Bézout.

au+bv=\text{PGCD}(a, b)\,

a, b sont connus et u, v et PGCD(ab) sont des nombres recherchés.

Comme vu plus haut, l'inverse modulaire u est solution de

au+nv=1,

a et n sont connus et v un entier qui sera éliminé. On se conforme ici à la forme que l'algorithme d'Euclide étendu résout, à la différence près que PGCD(an) = 1 est d'ores et déjà connu et non à calculer.

La complexité de l'algorithme est en O(log2(n)) quand |a| < n.

Théorème d'Euler[modifier | modifier le code]

Cette méthode est une alternative à l'algorithme d'Euclide : on peut utiliser le théorème d'Euler pour calculer l'inverse modulaire[1].

Selon ce théorème, si a est premier avec n, c'est-à-dire si PGCD(a, n) = 1, alors

a^{\varphi(n)} \equiv 1 \pmod{n}

où φ(n) est l'indicatrice d'Euler. Cela résulte du fait que a appartient au groupe des unités (ℤ/nℤ)* si et seulement si a est premier avec n. L'inverse modulaire est donc donné directement par

a^{-1}\equiv a^{\varphi(n)-1}\pmod n.

Dans le cas particulier où n est premier, l'équation ci-dessus devient :

a^{-1}\equiv a^{n-2}\pmod n.

Cette méthode de calcul reste généralement plus lente que l'algorithme d'Euclide, mais elle reste parfois utilisée quand on possède une implémentation de l'exponentiation modulaire. Elle souffre toutefois de plusieurs problèmes :

  • La connaissance de φ(n), dont le calcul le plus rapide reste la factorisation de n. Le problème de factorisation est un problème mathématique difficile qui est la source de la sûreté de l'algorithme RSA. Par contre, le calcul de φ(n) est trivial dans certains cas particuliers, comme quand n est une puissance d'un nombre premier.
  • L'exponentiation. Bien qu'implémentée plus efficacement en utilisant l'exponentiation modulaire, lorsqu'on traite de grandes valeurs de n l'efficacité augmente sensiblement en utilisant la méthode de réduction de Montgomery. Cet algorithme nécessite lui-même le calcul d'un inverse modulo n, ce qui était notre objectif au départ. Sans la méthode de Montgomery, il faut se contenter de l'algorithme de l'exponentiation rapide, ce qui calcule une division modulo n à chaque pas, problème conséquent quand n est grand. De toute manière, n'importe quelle exponentiation modulaire nécessite des étapes d'une complexité en O(log φ(n)) = O(log n).

Notes et références[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Modular multiplicative inverse » (voir la liste des auteurs)

  1. (en) Thomas Koshy, Elementary number theory with applications, 2e éd. (ISBN 978-0-12-372487-8, lire en ligne), p. 346

Articles connexes[modifier | modifier le code]