Posted on Laisser un commentaire

L’inversion modulaire

Partie I – Introduction contextuelle

L’inversion modulaire est un problème central en arithmétique et en théorie des groupes.
Il n’existe d’ailleurs, à ce jour, aucun algorithme vraiment efficace pour calculer l’inverse modulaire d’un (grand) entier. C’est d’ailleurs sur cette faiblesse que sont basés certains protocoles de cryptographie (comme la méthode RSA).

Fixons le contexte et voyons de quoi il s’agit…

Pour bien comprendre, commençons par un exemple où l’inverse modulaire n’existe pas…
Prenons deux entiers relatifs, par exemple a=6 et n=40 et posons-nous une question toute simple : existe-t-il un multiple de a tel que le reste de la division euclidienne de a par n soit égal à 1 ? Autrement dit, peut-on trouver un entier relatif u tel que :

au = nq + 1

On sait bien qu’une telle égalité ne peut se réaliser avec les valeurs choisies a=6 et n=40. En effet, au et nq sont tous les deux des entiers pairs, leur différence ne peut pas être égale à 1. Plus généralement, si a par n ont un diviseur commun d \geq 2, alors la quantité au-nq sera un multiple de d et ne pourra donc pas être égale à 1.

Mais si maintenant, on suppose que a et n sont des entiers premiers entre-eux, autrement dit si \text{PGCD}(a\,;\,n)=1, alors le problème énoncé ci-dessus admet des solutions. En effet, d’après le théorème de Bézout, il existe un couple (u\,;\, v) d’entiers relatifs tel que :

au + nv = 1

Ce qui s’écrit encore en terme de congruences :

au \equiv 1 \, [n]

On dit alors qu’un tel entier u est l’inverse de a modulo n.

Par exemple, 2 \times 4 \equiv 1 \, [7] ce qui signifie que l’inverse de 2 est 4 modulo 7. Bien sûr, on peut aussi dire que l’inverse de 4 est 2 modulo 7.

Bilan : nous venons de constater, grâce au théorème de Bézout, que l’inverse modulaire d’un entier a modulo n existe si et seulement si \text{PGCD}(a\,;\,n)=1. Mettons ce résultat en évidence car c’est un préalable à tout ce qui va suivre.

Théorème 1 – Condition d’existence de l’inverse modulaire

Soit n un entier naturel non nul.
Soit a un entier naturel compris entre 1 et n.
Alors le nombre a est inversible modulo n si et seulement si \text{PGCD}(a\,;\,n)=1.

Évidemment, les extrêmes que sont 0 et n ne seront jamais inversibles modulo n (excepté 1 qui est son propre inverse modulo 1). Les éventuels inversibles sont à chercher parmi les n-1 candidats que sont 1 \,;\, \dots \,;\, n-1.

Exemple : prenons n=45 et a=14. On a bien \text{PGCD}(a\,;\,n)=1 donc l’entier a=14 est inversible modulo n=45. Se pose maintenant une question essentielle : comment trouver cet inverse ?

En fait, nous connaissons déjà une façon de procéder : il suffit de déterminer une égalité de Bézout ! Pour cela, on peut appliquer l’algorithme d’Euclide-Bézout (appelé encore algorithme d’Euclide-étendu) voir la section arithmétique de nos questions «type-bac » (BAC S – spécialité Maths – Avec rappels de cours). Mais pour des « petits » nombres, on peut procéder de manière plus pragmatique en considérant la liste des multiples respectifs de a=14 et de n=45 :

Multiples de 14 :
0 ; 14 ; 28 ; 42 ; 56 ; 70 ; 84 ; 98 ; 112 ; 126 ; 140 ; 154 ; 168 ; 182 ; 196 ; 210 ; 224 ; 238  ; …
Multiples de 45 : 0 ; 45 ; 90 ; 135 ; 180 ; 225 ; 270 ; …

Il suffit de trouver dans ces listes, deux multiples respectifs dont la différence vaut 1. Ici, on a d’une part 224 = 14 \times 16 et d’autre part 225 = 45 \times 5. On peut donc écrire l’égalité de Bézout suivante :

14 \times (-16) + 45 \times 5 = 1

Autrement dit, en terme de congruences :

14 \times (-16) \equiv 1 \, [45]

Et comme -16 \equiv 29 \, [45], il est plus élégant d’écrire :

14 \times 29 \equiv 1 \, [45]

Nous avons prouvé que l’inverse de 14 modulo 45 est 29 !

Et en fait, en présence de petits nombres, on peut même oublier le théorème de Bézout et simplement lister les multiples de a puis réduire ces multiples modulo n jusqu’à tomber sur celui qui donne 1. Par exemple, quel est l’inverse de 9 modulo 11 ?

Multiples de 9 9 18 27 36 45
Réduction modulo 11 9 7 5 3 1

On constate, grâce à ce tableau que :

5 \times 9 \equiv 45 \equiv 1 \, [11]

Ce qui signifie que l’inverse de 9 modulo 11 est 5.
Cette technique algorithmique porte le nom de  « force brute » puisqu’on essaye tous les multiples possibles jusqu’à tomber sur le bon. Elle n’est pas efficace (en terme de rapidité d’algorithme) pour des grands entiers.

En quoi cela est important ces question d’inversion modulaire ? Imaginons que l’on souhaite résoudre une équation du genre 14x \equiv 3 \, [45]. Comment faire ? Eh bien, il suffit de multiplier de part et d’autre par l’inverse de 14, à savoir 29 pour obtenir :

29 \times 14 \times x \equiv 29 \times 3 \, [45]

Et puisque que 14 \times 29 \equiv 1 \, [45], on obtient :

x \equiv 57 \equiv 12 \, [45]

Ce genre de situation se rencontre par exemple dans le codage affine ou une fonction de codage est de la forme f : y \equiv ax + b \, [26] . Si on veut trouver la fonction affine réciproque qui permettra de décoder un message, il faut exprimer x en fonction de y. Pour cela, il suffit de multiplier de part et d’autre par l’inverse de a modulo 26. On se rend compte, au passage, que pour qu’une fonction affine de codage puisse être réversible (possibilité de décoder), il est nécessaire que l’entier a soit premier avec 26 (ou avec le nombre de caractères utilisés pour coder).

L’étude que nous venons de réaliser reste cependant un peu frustrante. Nous avons un algorithme (Euclide-Bézout) ou un algorithme de « force brute » qui permet de déterminer l’inverse modulaire mais ne pourrait-on pas aller plus loin afin d’avoir une formule ?

Partie II – La fonction indicatrice d’Euler

La fonction indicatrice d’Euler (mathématicien suisse, 1707 – 1783) apparaît, semble-t-il, pour la première fois, dans un écrit de ce dernier vers le milieu du XVIIIe siècle. Il s’agit, pour un entier naturel n non nul donné, de comptabiliser les entiers non nuls inférieurs à n qui sont premiers avec n. Ce nombre d’entiers est noté \varphi(n).

Définition – Fonction indicatrice d’Euler

Soit n \in \mathbb{N}^*. On note alors :

\varphi(n) = \text{Card}\{m \in [1\,;\,n] \cap \mathbb{N}, \text{PGCD}(m\,;\,n)=1\}

On a par exemple :

\varphi(15)=\text{Card}\{1\,;\,2\,;\,4\,;\,7\,;\,8\,;\,11\,;\,13\,;\,14\}=8

Et bien sûr, avec un nombre premier p, on obtient :

\varphi(p)=p-1 (et l’égalité \varphi(n)=n-1 est même un critère de primalité).

Et plus généralement, que vaut \varphi(p^k) lorsque p est premier (et k \in \mathbb{N}^*) ? Il suffit de constater que parmi les p^k entiers naturels non nuls inférieurs à p, tous seront premiers avec p^k excepté les multiples de p qui sont au nombre de p^{k-1} ainsi :

\varphi(p^k)=p^k-p^{k-1}=p^k\left(1-\frac{1}{p}\right)

Très bien, mais quel est le rapport entre l’inversion modulaire et cette fonction indicatrice d’Euler ? Nous y venons… Et ce rapport réside dans le théorème ci-dessous dû à Euler :

Théorème 1 – Théorème d’Euler

Soit n un entier naturel non nul.
Soit a un entier naturel compris entre 1 et n tel que \text{PGCD}(a\,;\,n)=1.
Alors :

a^{\varphi(n)} \equiv 1 \,[n]

Dès lors, l’inverse modulaire est tout trouvé ! En effet, on peut toujours écrire que a^{\varphi(n)} = a \times a^{\varphi(n)-1} si bien que l’inverse modulo n de a est tout simplement a^{\varphi(n)-1} :

a^{-1} \equiv a^{\varphi(n)-1} \, [n]

Nous avons enfin la formule tant recherchée !… Sauf que nous n’avons pas d’algorithme efficace pour calculer en un temps relativement court les nombres \varphi(n) lorsque n est un très grand entier…

Voir une démonstration du théorème d'Euler

Notons I_n l’ensemble des entiers non nuls m inférieurs à n et qui sont premiers avec n :

I_n = \{m \in [1\,;\,n] \cap \mathbb{N}, \text{PGCD}(m\,;\,n)=1\}

Par définition de l’indicatrice d’Euler, nous savons que le nombre d’éléments de l’ensemble I_n et \varphi(n) :

\varphi(n)=\text{Card}(I_n)

Soit a \in I_n et considérons l’application f_a qui à tout élément m de I_n associe le résidu modulo n de am :

\displaystyle \begin{array}{cccc}f_a :&I_n&\longrightarrow&I_n \\&m&\longmapsto&am \, [n]\end{array}

Montrons que l’application f_a est bijective.

L’application f_a est injective : supposons que l’on ait

f_a(m_1)=f_a(m_2)

am_1 \equiv am_2 \, [n]

Or, par hypothèse le nombre a est inversible modulo n, autrement dit a^{-1} existe. Multiplions la congruence précédente par a^{-1} :

a^{-1}am_1 \equiv a^{-1}am_2 \, [n]

m_1 \equiv m_2 \, [n]

Ce qui prouve l’injectivité de latex]f_a[/latex] (si deux éléments ont même image, ils sont identiques).

L’application f_a est surjective : soit s \in I_n. Nous allons montrer qu’il existe un élément s \in I_n tel que f_a(r)=s. Il suffit de poser r=a^{-1}s ainsi :

f_a(r) \equiv f_a(a^{-1}s) \equiv a a^{-1}s \equiv s \, [n]

Ce qui prouve la surjectivité f_a (tout élément de l’ensemble d’arrivée est atteint).

Conclusion : l’application f_a est bijective.

Notons maintenant \alpha_1, \alpha_2,…, \alpha_{\varphi(n)}, les \varphi(n) éléments de I_n :

I_n = \{\alpha_1\,;\,\alpha_2\,;\,\dots\,;\,\alpha_{\varphi(n)}\}

Par définition de I_n, tous ces entiers \alpha_k (pour 1 \leq k \leq \varphi(n)) sont inversibles modulo n.

Mais puisque l’application f_a est bijective, ces \varphi(n)  éléments peuvent encore se noter a\alpha_1, a\alpha_2,…, a\alpha_{\varphi(n)} :

I_n = \{a\alpha_1\,;\,a\alpha_2\,;\,\dots\,;\,a\alpha_{\varphi(n)}\}

Multiplions maintenant entre-eux tous les éléments de I_n. D’une part, avec la première liste d’éléments et d’autre part avec la seconde liste d’éléments (on obtient donc le même produit final) tout cela donne modulo n :

\displaystyle \prod_{k=1}^{\varphi(n)} \alpha_k \equiv \prod_{k=1}^{\varphi(n)} a\alpha_k \, [n]

\displaystyle \prod_{k=1}^{\varphi(n)} \alpha_k \equiv a^{\varphi(n)}\prod_{k=1}^{\varphi(n)} \alpha_k \, [n]

Et en multipliant par \prod_{k=1}^{\varphi(n)} \alpha_k^{-1}, il reste :

a^{\varphi(n)}\equiv 1\,[n]

Ce qui prouve le théorème d’Euler.

Remarque : avec les notations du supérieur, l’ensemble I_n est le groupe des éléments inversibles de \left(\mathbb{Z}/n\mathbb{Z}\right) (ensemble des classes d’équivalences pour la relation d’équivalence modulo n) :

I_n=\left(\mathbb{Z}/n\mathbb{Z}\right)^*

Le problème de l’inversion modulaire reste donc une difficulté en terme de rapidité d’algorithme de calcul. Sauf cas particuliers ; en effet, l’inverse modulaire de 1 est toujours 1 car on peut toujours écrire 1 \times 1 \equiv 1 \, [n]. Un autre cas est très simple également : il s’agit de l’inverse modulaire de (n-1) modulo n. Il sera toujours son propre inverse ! En effet, cela est dû à la classique identité remarquable suivante :

(n-1) \times (n-1) \equiv n^2 - 2n + 1 \equiv 1 \, [n]

Donc :

(n-1)^{-1} \equiv (n-1) \, [n]

Avant de passer à la suite, on ne peut pas passer sous silence l’incontournable petit théorème de Fermat qui peut se voir comme un cas particulier du théorème d’Euler lorsque le nombre n est un nombre premier p.

Théorème 1 – Petit théorème de Fermat

Soit p un nombre premier.
Soit a un entier naturel non divisible par p.
Alors :

a^{p-1} \equiv 1 \,[p]

Voir une démonstration du petit théorème de Fermat

Cas 1 : si a est un entier strictement inférieur à p alors on a \text{PGCD}(a\,;\,p)=1 car p est premier et pour la même raison, on a \varphi(p)=p-1 et d’après le théorème d’Euler :

a^{p-1} \equiv a^{\varphi(p)} \equiv 1 \, [p]

Cas 2 : si maintenant a est un entier strictement supérieur à p alors on pose a' le reste de la division euclidienne de a par p ainsi :

a' \equiv a \, [p]  et  0 < a' < p

La condition 0 <a' découle du fait que a n’est pas un multiple de p.

Il reste à élever la relation a' \equiv a \, [p] à l’exposant p-1 et à appliquer le cas 1 à l’entier a' :

a^{p-1} \equiv a'^{p-1} \equiv 1 \, [p]

 

Partie III – Tableaux des inverses modulaires

\boxed{n=2} \ ; \ \varphi(2)=1
Inverse modulo 2
Nombre a 1
Inverse a^{-1} 1
\boxed{n=3} \quad;\quad \varphi(3)=2
Inverses modulo 3
Nombre a 1 2
Inverse a^{-1} 1 2
\boxed{n=4} \quad;\quad \varphi(4)=2
Inverses modulo 4
Nombre a 1 3
Inverse a^{-1} 1 3
\boxed{n=5} \quad;\quad \varphi(5)=4
Inverses modulo 5
Nombre a 1 2 3 4
Inverse a^{-1} 1 3 2 4
\boxed{n=6} \quad;\quad \varphi(6)=2
Inverses modulo 6
Nombre a 1 5
Inverse a^{-1} 1 5
\boxed{n=7} \quad;\quad \varphi(7)=6
Inverses modulo 7
Nombre a 1 2 3 4 5 6
Inverse a^{-1} 1 4 5 2 3 6
Voir les suivants
\boxed{n=8} \quad;\quad \varphi(8)=4
Inverses modulo 8
Nombre a 1 3 5 7
Inverse a^{-1} 1 3 5 7
\boxed{n=9} \quad;\quad \varphi(9)=6
Inverses modulo 9
Nombre a 1 2 4 5 7 8
Inverse a^{-1} 1 5 7 2 4 8
\boxed{n=10} \quad;\quad \varphi(10)=4
Inverses modulo 10
Nombre a 1 3 7 9
Inverse a^{-1} 1 7 3 9
\boxed{n=11} \quad;\quad \varphi(11)=10
Inverses modulo 11
Nombre a 1 2 3 4 5 6 7 8 9 10
Inverse a^{-1} 1 6 4 3 9 2 8 7 5 10
\boxed{n=12} \quad;\quad \varphi(12)=4
Inverses modulo 12
Nombre a 1 5 7 11
Inverse a^{-1} 1 5 7 11
\boxed{n=13} \quad;\quad \varphi(13)=12
Inverses modulo 13
a 1 2 3 4 5 6 7 8 9 10 11 12
a^{-1} 1 7 9 10 8 11 2 5 3 4 6 12
\boxed{n=14} \quad;\quad \varphi(14)=6
Inverses modulo 14
Nombre a 1 3 5 9 11 13
Inverse a^{-1} 1 5 3 11 9 13
\boxed{n=15} \quad;\quad \varphi(15)=8
Inverses modulo 15
Nombre a 1 2 4 7 8 11 13 14
Inverse a^{-1} 1 8 4 12 2 11 7 14
\boxed{n=16} \quad;\quad \varphi(16)=8
Inverses modulo 16
Nombre a 1 3 5 7 9 11 13 15
Inverse a^{-1} 1 11 13 7 9 3 5 15
\boxed{n=17} \quad;\quad \varphi(17)=16
Inverses modulo 17
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
a^{-1} 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16
\boxed{n=18} \quad;\quad \varphi(18)=6
Inverses modulo 18
Nombre a 1 5 7 11 13 17
Inverse a^{-1} 1 11 13 5 7 17
\boxed{n=19} \quad;\quad \varphi(19)=18
Inverses modulo 19
a 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
a^{-1} 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18
\boxed{n=20} \quad;\quad \varphi(20)=8
Inverses modulo 20
Nombre a 1 3 7 9 11 13 17 19
Inverse a^{-1} 1 7 3 9 11 17 13 9
\boxed{n=21} \quad;\quad \varphi(21)=12
Inverses modulo 21
a 1 2 4 5 8 10 11 13 16 17 19 20
a^{-1} 1 11 16 17 8 19 2 13 4 5 10 20
\boxed{n=22} \quad;\quad \varphi(22)=10
Inverses modulo 22
a 1 3 5 7 9 13 15 17 19 21
a^{-1} 1 15 9 19 5 17 3 13 7 21
Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

CAPTCHA
Change the CAPTCHA codeSpeak the CAPTCHA code
 

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.