Introduction

Le déchiffrement du message est aussi simple, il suffit de faire tourner le disque extérieur de \(k\) po­si­tions dans le sens horaire à partir de deux disques synchrones.

OAYNUQZPQFQZFMFUHQEMHQLHAGERMUFQEBAGDFDAGHQDW

La quantité secrète que seul César et ses généraux connaissaient est bien sûr le décalage \(k\) utilisé, il constitue la clef secrète. Un tel système est appelé chiffrement à clé secrète. Il est évident que le chif­fre­ment de César n'est pas sûr dès que le texte chiffré comporte quelques lettres (il est en revanche inviolable si le message ne contient qu'une seule lettre). Même si elle est fastidieuse, sa cryptanalyse*(*) Tech­ni­ques mises en œuvre pour dé­chif­frer un mes­sa­ge dont on ne con­naît pas la clef. peut se faire à la main, en tentant les différents décalages \(k\) possibles. On peut faire mieux en cherchant la lettre la plus fréquente du message chiffré et supposer qu'il s'agit du chiffré de la lettre \(E\). En effet, la lettre \(E\) est la plus fréquente (de la langue française) et les chiffrés ont la même fréquence d'apparition que les clairs puisqu'il s'agit d'une bijection. Une fois cette lettre trouvée, la clef \(k\) est la distance qui sépare \(E\) de cette lettre.

Aujourd'hui les systèmes de chiffrement à clef secrète utilisés sont bien plus robustes et bien plus complexes à cryptanalyser. Néanmoins tous ont le même défaut, il faut partager la clef secrète avec les destinataires légitimes avant de leur transmettre des messages chiffrés. Si la transmission manuelle des clés était de mise à l'époque de Jules César, la dématérialisation des données et les transmissions électroniques d'aujourd'hui s'accomodent mal de méthodes aussi rudimentaires. Il faut donc disposer d'un canal de transmission sécurisé pour transmettre les clés, mais dans ce cas pourquoi ne pas transmettre le message en clair via ce canal puisqu'il est sûr ?

Il faut alors trouver un moyen de transmettre des clefs secrètes sur un canal non sécurisé. Cela peut semb­ler impossible, et pourtant ce problème a été résolu à la fin des années 1970. L'un des premiers protocoles de chiffrement à clé publique proposé fut rsa, acronyme de ses concepteurs, Ronald Rivest, Adi Shamir et Leonard Adleman. Il est toujours utilisé intensivement aujourd'hui. L'objectif de ce chapitre est de comprendre comment ces chercheurs ont pu réaliser ce tour de force. Pour cela, il faut connaître quelques résultats élémentaires (mais rarement triviaux) en ari­thmé­ti­que. L'ari­thmé­ti­que est la branche des mathématiques qui étudie les propriétés des nombres ra­tion­nels. Ces propriétés sont principalement liées aux interactions entre les deux lois de composition internes, l'addition et la multiplication ainsi que la relation d'ordre naturel sur l'ensemble \(\Z\).

Les groupes quotients de \({\mathbb Z}\)

Nous reprenons l'étude des groupes entamée au chapitre Groupes à travers un cas particulier fondamental, le groupe additif \((\Z,+)\).

Divisibilité, nombres premiers

Nous avons défini la relation de divisibilité sur l'ensemble des entiers naturels \(\N\), cette relation s'étend à l'ensemble des entiers relatifs.

Par exemple, \(3\mid15\) et \(5\mid15\). Cette relation binaire est réflexive, en effet \(a.1=a\). Elle est également transitive puisque si \(a\mid b\), il existe \(x\in\Z\) tel que \({\color{#FF8}ak}={\color{#FF8}b}\) et si \({\color{#FF8}b}\mid c\), il existe \(l\in\Z\) tel que \({\color{#FF8}b}l=c\), donc \(({\color{#FF8}ak})l=a(kl)=c\) soit \(a\mid c.\) On qualifie parfois une telle relation de préordre. En revanche elle n'est pas symétrique puisque \(2\mid 4\) mais \(4\not\mid 2\), donc ce n'est pas une relation d'équivalence sur \(\Z\). Ce n'est pas non plus une relation d'ordre sur \(\Z\), con­trai­re­ment à la di­vi­si­bi­li­té dans \(\N\). La divisibilité dans \(\Z\) n'est pas antisymétrique, en effet, pour tout entier naturel \(n\not = 0\), \(n\mid(-n)\) et \((-n)\mid n\) et pourtant \(n\not = (-n)\).

On définit la valeur absolue d'un entier relatif \(k\), que l'on note \(\def\abs#1{{|\,#1\,|}}\abs{k}\), comme le maximum de l'en­semb­le \(\{-k,k\}\) pour la relation d'ordre naturel définie sur \(\Z\) par \(x\leq y\Leftrightarrow y-x\in\N\).

Le théorème qui suit est central en ari­thmé­ti­que. Il est très intuitif puisqu'il s'agit de partager \(a\) bonbons entre \(b\) amis. C'est un résultat très profond utilisé au sein de nombreuses démonstrations.

Revenons sur les entiers naturels et par­ti­cu­liè­re­ment sur les nombres premiers. Sont-ils nombreux ? Comment les calculer ?

Pour trouver des nombres premiers, Eratosthène*(*) Eratosthène était un savant grec, à la fois mathématicien, géo­gra­phe, ast­ro­no­me et poète et qui di­ri­geait la gran­de bi­blio­thè­que d'Ale­xan­drie deux siècles et demi avant jc. Il avait, entre autres, estimé la cir­con­fé­ren­ce de la Ter­re. a proposé une méthode simple et élégante qui porte aujourd'hui son nom, le crible d'Eratosthène. Le principe est le suivant. On se donne un entier \(N > 1\) arbitraire et on constitue initialement la liste de tous les entiers compris entre \(1\) et \(N\). L'al­go­ri­thme va éliminer (cribler) tous les nombres de cette liste qui ne sont pas premiers. On ini­tia­li­se le processus en criblant le nombre 1 car il n'est pas premier. On cherche ensuite le prochain nombre \(p\) de la liste qui n'est pas criblé, à savoir 2 et on crible tous ses multiples \(kp\) pour \(k > 1\). On re­com­men­ce en cherchant le prochain nombre \(p\) qui n'est pas criblé dans la liste, c'est-à-dire 3, et on crible ses multiples \(kp\) pour \(k > 1\), etc. jusqu'à ce que \(p^2 > N\) :

Crible(N)
ENTRÉE: un entier naturel N
SORTIE: une liste de booléens EstPremier[1:N] telle que
        (EstPremier[p]) ⇔ (p premier)

EstPremier[1:N] ← N*[VRAI]
EstPremier[1] ← FAUX
p ← 1
TANT QUE (p2 ≤ N):
   p ← p + 1
   TANT QUE (p2 ≤ N) ET (NON EstPremier[p]):
      p ← p + 1
   k ← 2
   TANT QUE (k*p ≤ N):
      EstPremier[k*p] ← FAUX
      k ← k + 1
RENVOYER EstPremier

Les nombres premiers qui apparaissent en jaune à la fin du crible sont les nombres premiers \({\color{#FF8}p}\) utilisés dans la boucle qui crible leurs multiples (instructions #13 à #15).

Soit (\(k_i)_{i\in\llbracket 1,\,\ell\rrbracket }\) une séquence croissante d'entiers naturels (i.e. l'application \(k:\llbracket 1,\,\ell\rrbracket \rg\N\) définie par \(i\mapsto k_i\) est croissante). Si l'on peut écrire un entier naturel \(n\) sous la forme du produit

alors on dit que \((k_i)_{i\in\llbracket 1,\,\ell\rrbracket }\) est une décomposition en produit de facteurs croissants de \(n\). Une telle décomposition existe toujours puisque la séquence constitué du seul entier \(n\) fait l'affaire. Un entier naturel peut admettre plusieurs décompositions en produit de facteurs croissants :

Attention, la rapidité avec laquelle notre script réalise la décomposition de l'entier \(N\) n'est qu'ap­pa­ren­te. Nous verrons dans le cours d'Algorithmique que cet algorithme est inef­fi­ca­ce.

Nous arrêterons là nos investigations sur les nombres premiers pour la pre­miè­re année mais une multitude d'autres questions se posent. Par exemple, comment sont-ils répartis ? Peut-on les calculer avec une formule ? Est-il facile de déterminer si un nombre est premier ?

Congruences

Soit \(n\in\N\). Dans la suite, on note \(n\Z\) l'ensemble des multiples de \(n\) défini par \begin{equation} n\Z:=\{nz\mid z\in\Z\}. \end{equation}

Rappelons que les relations d'équivalence compatibles avec une loi de composition interne sur un groupe \((G,+)\) sont nécessairement de la forme \(y-x\in H\) où \(H\) est un sous-groupe normal de \(G\) (cf. théorème).*(*) La loi de groupe est ici notée ad­di­ti­ve­ment, le sy­mé­tri­que est donc no­té com­me un op­po­sé \(-x\) au lieu d'un in­ver­se \(x^{-1}\). Deux entiers relatifs \(x\) et \(y\) sont dit congrus modulo \(n\) si leur différence est un multiple de \(n,\) ce que l'on note \(x\equiv y\pmod n.\)

On peut donc quotienter le groupe \((\Z,+)\) par \(n\Z\), le quotient \((\Z/n\Z,+)\) héritant de la loi quotient additive de \(\Z\). Notons que si deux entiers relatifs \(x\) et \(y\) sont congrus modulo \(n\), on écrit \(x\equiv y\pmod n\) alors que si ce sont deux éléments de \(\Z/n\Z\) qui sont congrus modulo \(n\) alors \(x=y\).

Ainsi dans \(\Z/6\Z\), pour calculer \(\overline{4}+\overline{5}\), il suffit d'additionner \(4+5=9\) et de calculer le reste de la division euclidienne de \(9\) par \(6\) pour obtenir \(3\).

Le théorème suivant est très important, il dit en substance que les seuls groupes monogènes sont les groupes \(\Z\) ou \(\Z/n\Z\).

On rappelle que l'ordre d'un élément \(a\) d'un groupe fini \(G\) est l'ordre du sous-groupe monogène \(\text{gr}(a)\) de \(G\) qu'il engendre. Le théorème suivant n'est rien d'autre que le théorème de Lagrange.

Exemple : d'après ce théorème nous savons que l'ordre de chaque entier de \(0\) à \(9\) divise \(9\) dans \(\Z/9\Z\). Cette proposition nous dit que cet ordre n'est autre que \(9\) pour ceux qui sont premiers avec \(9\), à savoir les entiers \(1,\) \(2,\) \(4,\) \(5,\) \(7,\) et \(8.\) Calculons l'ordre des trois autres valeurs, \(0\), \(3\), et \(6\). Le sous-groupe additif engendré par \(0\) est le singleton \(\{0\}\), il est donc d'ordre \(1\). Le sous-groupe additif engendré par \(3\) est l'ensemble \(\{3,6,0\}\), il est d'ordre \(3\). Le sous-groupe additif engendré par \(6\) est le même que celui engendré par \(3\).

Les anneaux \({\mathbb Z}/n{\mathbb Z}\)

Structure d'anneau.

L'ensemble \(\Z\) est muni de deux lois de composition internes, l'addition et la multiplication dont les propriétés lui confèrent une structure d'anneau.

Nous savons déjà d'après l'étude menée sur \((\Z,+)\) et \((\Z,\times)\) dans les précédents chapitres qu'il s'agit d'un anneau commutatif. Le triplet \((\R,+,\times)\) est également un anneau commutatif et même un corps puisque tout réel non-nul admet un inverse.

Nous ne démontrerons pas les règles de calcul bien connues du lecteur depuis le lycée sur l'anneau \(\Z\) (règle des si­gnes, \(0.x=x.0=0\), etc.) Nous avons déjà vu la formule du binôme de Newton au chapitre Combinatoire.

Quand nous avons étudié la relation de divisibilité, dans \(\N\) ou dans \(\Z\), nous avons remarqué que tous les entiers sont des diviseurs de \(0\) puisque \(\forall a\in\Z\ a.0=0\). Dans le contexte des anneaux, on déroge à la définition générale pour \(0\) car il y joue un rôle particulier :

Dans un anneau intègre, comme \(\Z\) par exemple, on a donc

En effet, la multiplication dans un anneau \(A\) est associative et on sait (cf. cette proposition) que le produit de deux éléments inversibles est inversible, donc \(A^\times\) est stable pour la multiplication. L'élé­ment neutre 1 est inversible, son inverse est lui-même et l'inverse \(x^{-1}\) de \(x\) est in­ver­si­ble (c'est \(x\)) donc \(x^{-1}\in A^\times\), finalement \((A^\times,\times)\) est un groupe.

Pour le corps \((\R,+,\times)\), on a \(\R^\times=\R\setminus\{0\}\). Pour l'anneau \((\Z,+,\times)\), on a \(\Z^\times=\{-1,1\}\).

Idéaux et anneaux quotients

Nous nous sommes intéressés à la structure de groupe additif de \(\Z\), nous avons montré que tous ses sous-groupes sont de la forme \((n\Z,+)\) et qu'ils sont tous normaux puisque le groupe \((\Z,+)\) est com­mu­ta­tif. Cela nous a permis de construire le groupe additif quotient \((\Z/n\Z,+)\). La question qui se pose à présent concerne la loi multiplicative, le groupe quotient \((\Z/n\Z,+)\) peut-il hériter également de la mul­ti­pli­ca­tion de \(\Z\) pour en faire un anneau ?

Nous verrons que la réponse est oui si ce groupe est stable pour la multiplication par n'importe quel élément de l'anneau. La méthodologie pour y arriver sera la même que celle que nous avons menée dans le chapitre Groupes. L'objectif est encore une fois de munir l'ensemble quotient d'une structure qui assure que la surjection canonique soit un morphisme, mais cette fois le morphisme doit respecter les deux struc­tu­res, additive et multiplicative. Pour ne pas alourdir inutilement les éc­ri­tu­res, on note de la même façon les lois additives et multiplicatives d'anneaux distincts :

La première condition indique que \(f\) est un morphisme du groupe additif \((A,+)\) de l'anneau \(A\). Pour qu'une partie \(B\subseteq A\) munie des lois induites par celles de \(A\) constitue elle aussi un anneau, il faut que \((B,+)\) soit un sous-groupe de \((A,+)\) stable pour la multiplication et qui contient \(1_A\). Ainsi le seul sous-anneau de \(\Z\) est nécessairement \(\Z\) lui-même puisque \((\Z,+)\) est le seul sous-groupe de \((\Z,+)\) qui contient \(1\).

On obtient aisément des résultats similaires à ceux que nous avons obtenus pour les sous-groupes d'un groupe et les morphisme de groupes. Ainsi, si \(f:A\rg A'\) est un morphisme d'anneaux, et \(B\) et \(B'\) sont respectivement des sous-anneaux de \(A\) et \(A'\), alors \(f^{-1}(B')\) et \(f(B)\) sont des sous-anneaux de \(A\) et \(B\) respectivement. D'autre part, l'intersection de sous-anneaux d'un anneau est encore un anneau, on peut donc définir le sous-anneau engendré par une partie \(B\) quelconque d'un anneau \(A\) comme l'intersection de tous les sous-anneaux de \(A\) qui contiennent \(B\).

La deuxième condition exprime que le sous-groupe additif est stable pour la multiplication (à gauche ou/et à droite) par un élément de l'anneau tout entier. Dans un anneau commutatif, comme \(\Z\) par exemple, tout idéal est nécessairement bilatère. Nous connaissons les sous-groupes additifs de \(\Z\), ce sont les ensembles du type \(n\Z:=\{nz\mid z\in\Z\}\), au­tre­ment dit l'ensemble des multiples de \(n\). Si l'on multiplie un multiple d'un entier \(n\) par n'importe quel entier, on obtient toujours un multiple de \(n\), autrement dit la condition 2 est toujours satisfaite, donc

Les groupes quotients \((\Z/n\Z,+)\) ont été obtenus à l'aide des seules relations d'équivalences \(\rel\) compatibles avec l'addition, à savoir celles qui satisfont \(x{\rel}x'\iff x-x'\in n\Z\) où \((n\Z,+)\) est un sous-groupe (nécessairement normal) de \((\Z,+)\). Mais cette relation est-elle compatible avec la mul­ti­pli­ca­tion, c'est-à-dire satisfait-elle la proposition

La réponse est affirmative puisque si \(x-x'\in n\Z\), alors il existe \(z\in\Z\) tel que \(x-x'=nz\) et donc \(xy-x'y=n(yz)\) donc \(xy{\rel}x'y\). On peut donc munir \(\Z/n\Z\) de la loi quotient \(\times\) héritée de \(\Z\).

La surjection canonique \(\varphi:\Z\rg\Z/n\Z\) est donc non seulement un morphisme additif, mais également un morphisme d'anneaux.

Application: critères de divisibilité.

Bien que cette pratique soit devenue désuète, à tort, nous allons étudier la preuve par 9. Soit \(n\in\N\), \(x\) et \(y\) deux éléments de \(\Z\) et \(\varphi\) la surjection canonique de \(\Z\) sur \(\Z/n\Z\). Comme \(\varphi\) est un morphisme d'anneaux, on a \begin{align*} \varphi(x+y)&=\varphi(x)+\varphi(y),\\ \varphi(xy)&=\varphi(x)\varphi(y). \end{align*} Autrement dit le reste modulo \(n\) d'une somme (ou d'un produit) doit être égal à la somme des restes (ou le produit des restes). C'est donc une condition nécessaire (mais pas suffisante). Prenons par exemple \(n=2\) et observons la proposition suivante : \begin{equation} \label{eq:sample} 121+4195=4327. \end{equation} Elle est fausse bien sûr, et l'argument le plus simple pour s'en convaincre est que la somme de deux nombres impairs est un nombre pair, or ici le résultat est impair. Transportons ce calcul dans \(\Z/2\Z\) via la surjection canonique que nous noterons \(\varphi_2\) : \begin{align*} \varphi_2(121)+\varphi_2(4195)&=\varphi_2(4237)\\ 1+1&=1\\ {\color{red}0}&{\color{red}\;=1}\\ \end{align*} On aurait pu faire de même avec n'importe quelle autre valeur de \(n\), par exemple \(n=13\), \begin{align*} \varphi_{13}(121)+\varphi_{13}(4195)&=\varphi_{13}(4237)\\ 4+9&=12\\ {\color{red}0}&{\color{red}\;=12}\quad\text{car}\ 4+9\equiv 0\ \text{mod}\ 13. \end{align*}

Le lecteur perspicace fera deux objections. La première est que détecter une erreur de calcul en le plongeant dans \(\Z/13\Z\) semble encore plus fastidieux que de refaire ce calcul puisqu'il faut calculer le reste de la division euclidienne par 13, ce qui n'est pas aisé à faire de tête. La seconde est que si la vérification d'un calcul dans \(\Z/2\Z\) est beaucoup plus simple, elle manque singulièrement de fiabilité. En effet pour tout triplet \((x,y,z)\) de valeurs paires (resp. impaires) dans \(\Z\) l'équation \(x+y=z\) se traduira toujours par \(0+0=0\) (resp. \(1+1=1\)) et laisse passer beaucoup (c'est un eu­phé­mi­sme) de faux calculs dans les mailles grossières de ce filet.

Continuons malgré tout. Les multiples représentations des nombres sont étudiées dans un cours d'informatique générale ou d'architecture des ordinateurs de première année, nous supposons donc que le lecteur connaît quelques ru­di­ments sur la question. Notre système de numération permet de représenter un entier naturel à l'aide de chiffres. Quand on écrit \(a=2305\) en base 10, ceci se traduit par

Et plus généralement un entier \(a\) de \(k+1\) chiffres en base \(B\) s'écrit

Si \(\varphi_n\) désigne la surjection canonique de \(\Z\) dans \(\Z/n\Z\), on a nécessairement

Posons \(n:=B-1\), alors le reste de la division euclidienne de \(B\) par \(n\) est \(1\) puisque \(B=1.(B-1)+1\), donc \(\varphi_{n}(B)=1\). D'autre part, \begin{equation} \varphi_n(a_i)= \begin{cases} a_i&\text{si}\ a_i < n.\\ {\color{green}0}&\text{si}\ a_i=n.\\ \end{cases} \end{equation} mais le calcul de la somme dans \((\ref{eq:modulon})\) se faisant modulo \(n\), ont peut différer la réduction à \(0\) pour les chiffres \(a_i=n\) après l'addition :

Concrètement, il suffit de faire la somme modulo \(n\) des chiffres qui constituent le nombre (en évitant, si on veut aller plus vite, les valeurs égales à \(n\)), pour calculer son reste modulo \(n.\) Reprenons l'exemple \((\ref{eq:sample})\) en base \(B=10\) pour laquelle \(n=9\) :

Notons que le même procédé d'invalidation du calcul pour l'égalité \(121+4195=4325\) aurait échoué puisque \(4+3+2+5\equiv 5\ \text{mod}\ 9\) alors que le bon résultat est \(4316\). La preuve par \(9\) ne permet donc pas de prouver qu'une opération a été effectuée correctement mais de prouver parfois qu'elle est fausse.

Algorithme d'Euclide, identité de Bézout

PGCD, algorithme d'Euclide.

Soit \(z\in\Z\). On note \(D_z:=\{d\in\Z\such d\mid z\}\) l'ensemble des diviseurs de \(z\). Il est clair que \(D_z=\Z\iff z=0\). On se donne deux entiers relatifs \(a\) et \(b\) et on veut étudier leurs diviseurs communs, autrement dit l'intersection \(D:=D_a\cap D_b\), dans le cas où l'un des deux entiers n'est pas nul, sans quoi \(D_a\cap D_b=\Z\).

L'ensemble \(D\cap\N\) n'est pas vide puisque \(1\mid a\) et \(1\mid b\). D'autre part, supposons que \(a\neq 0\), sinon on fait le même raisonnement avec \(b\), alors \(D\cap\N\) est majoré par \(\abs{a}\) puisque \(D_a\) est majoré par \(\abs{a}\) et \(D\) est inclus dans \(D_a\). L'ensemble \(D\cap\N\) est une partie non-vide et majorée de \(\N\), elle admet donc un plus grand élément :

Comme nous l'avons vu, si \(a=b=0\) l'ensemble des diviseurs commun de \(a\) et \(b\) est l'ensemble \(\Z\) tout entier qui n'admet pas de plus grand élément. On convient en général de poser la convention \((0,0):=0\).

On peut calculer le pgcd de deux entiers sans connaître leurs décompositions en produits de facteurs premiers. C'est Euclide*(*) Mathématicien grec qui vécut 300 ans avant jc. qui décrivit la première fois comment procéder.

L'identité \((\ref{eq:pgcdbis})\) suggère un algorithme du calcul pgcd de deux entiers \(a\) et \(b\) plus efficace que de répéter des soustractions (l'algorithme d'Euclide). Il suffit d'appliquer une seule division euclidienne à chaque étape jusqu'à ce que le reste soit nul, le quotient de la dernière division fournit le résultat :

PGCD(a,b)
ENTRÉE: deux entiers naturels a, b
SORTIE: le PGCD (a,b)

TANT QUE (b > 0):
   t ← b
   b ← a MOD b
   a ← t
RENVOYER a

Notons que si \(a < b\), le premier passage dans la boucle échange les valeurs de \(a\) et \(b\) ce qui évite de les comparer avant d'entrer dans la boucle.

Et en anticipant sur la version étendue de cet algorithme qui sera étudiée plus loin, on ob­tient un couple \((u,v)=\,\) solution de l'identité de Bézout :

Identité de Bézout

Si \(I\) et \(J\) désignent deux idéaux d'un anneau commutatif \(A\), on appelle idéal somme de \(I\) et \(J\), que l'on note \(I+J\), l'intersection de tous les idéaux de \(A\) qui contiennent toutes les sommes \(au+bv\) où \((a,b)\in I\times J\) et \((u,v)\in A^2\). Comme les idéaux de \(\Z\) sont du type \(n\Z\), l'idéal somme \(a\Z+b\Z\) est le plus petit idéal qui contient les sommes du type \(au+bv\) puisque les éléments de ces idéaux de \(\Z\) sont déjà des multiples de \(a\) et \(b\).

Notons que le théorème n'affirme pas que le couple solution \((u,v)\) est unique, nous y reviendrons. À quoi peut servir l'identité de Bézout ? Une première réponse est fournie par le corollaire sui­vant qui établit un nouveau critère pour déterminer si deux nombres sont premiers entre eux.

Une conséquence très importante de ce corollaire est de fournir un moyen de calculer l'inverse d'un élé­ment \(x\) de \((\Z/n\Z)^\times\). On peut bien sûr s'appuyer sur la table de multiplication et chercher où se trouve la valeur \(1\) sur la ligne d'entrée \(x\), mais même en ne faisant que la moitié des opérations grâce à la commutativité de \(\Z/n\Z\), cela en nécessite \(\frac{n^2}{2}\). Nous verrons à la dernière section que la cryptographie fait un usage immodéré de cet anneau modulaire pour des entiers \(n\) qui comportent plus de 600 chiffres*(*) Ce n'est pas une co­quil­le, il s'agit bien d'en­tiers \(n\) proches de \(10^{616}\). en base 10, et la mémoire de tous les ordinateurs de la planète réunie ne suffirait pas à contenir cette table de mul­ti­pli­ca­tion.

Un couple qui satisfait \((\ref{eq:bezout1})\) permet de calculer l'inverse d'un élément \(x\in(\Z/n\Z)^\times\). En effet, soit \(x\) un entier premier avec \(n\), condition nécessaire et suffisante pour que \(x\) admette un inverse. C'est là que le corollaire entre en scène, si \(x\) est premier avec \(n\), on sait qu'il existe un couple \((u,v)\) tel que \(xu+nv=1\) et donc \begin{equation} xu\equiv 1\ (\text{mod}\ n). \end{equation} Autrement dit, l'entier \(u\) est l'inverse de \(x\) dans \(\Z/n\Z\). Mais nous n'avons fait que re­pous­ser le problème. L'identité de Bézout et son corollaire sont des théorèmes existentiels et pas des théorèmes constructifs, ils ne fournissent pas d'algorithmes pour construire le couple \((u,v)\). Heureusement, il en existe.

Algorithme d'Euclide étendu

D'après l'identité de Bézout \((\ref{eq:Bézout})\), l'équation n'a de solution que si \((a,b)\mid d\) et en particulier si \(d=(a,b)\). Si nous déterminons un couple \((u,v)\in\Z^2\) tel que \(au+bv=(a,b)\), alors pour tout entier \(d\) multiple de \((a,b)\), le couple \((u\frac{d}{(a,b)},v\frac{d}{(a,b)})\) satisfera l'identité de Bézout \begin{equation} a(u\frac{d}{(a,b)})+b(v\frac{d}{(a,b)})=d \end{equation}

C'est en observant attentivement la construction du pgcd avec l'algorithme d'Euclide que l'on peut construire un couple \((u,v)\) qui satisfait \(au+bv=(a,b)\). Observons la suite des divisions euclidiennes effectuées pour obtenir \((192,57)=\boxed{3}\) en précisant leurs quotients et leurs restes :

Isolons les restes dans chacune de ces identités (sauf la dernière où il est nul). C'est donc l'avant dernier reste \((\ref{eq:box1})\) qui fournit le pgcd \(\boxed{3}\) :

On reconnaît ici autant d'identités de Bézout avec leurs solutions \(({\color{#F62}u},{\color{#88F}v})\) respectives. L'idée est de faire remonter la valeur \(3\) jusqu'à la première égalité à l'aide de simples additions et multiplications. En multipliant l'égalité \((\ref{eq:box2})\) par le coefficient \({\color{#88F}v=-2}\) de l'entier \(\boxed{6}\) dans l'égalité \((\ref{eq:box3})\), on obtient un nouveau système :

On additionne alors les deux dernières égalités \((\ref{eq:box4})\) et \((\ref{eq:box5})\) pour éliminer \(\boxed{6\,.\,(-2)}\) de part et d'autre du résultat pour obtenir l'identité de Bézout \((\ref{eq:box6})\)  :

Et on fait remonter ainsi \(3\) de proche en proche :

Soit

Et donc

Pour obtenir finalement

Notons \((q_i)_{i\in\llbracket 1,\,n\rrbracket }\) les \(n\) premiers quotients des \(n+1\) divisions euclidiennes qui ont été effectuées suc­ces­si­ve­ment pour calculer \((a,b)\). Alors le couple solution de la \(i\)-ème identité de Bézout cor­res­pon­dan­te est égal à \((1,-q_i)\). Dans notre exemple, on avait \[(q_1,q_2,q_3,q_4)=(3,2,1,2).\]

Chaque remontée du pgcd consiste en une multiplication et une addition de l'identité de Bézout précédente, modifiant du coup les valeurs du couple solution de cette identité. Notons \((u,v)\) le couple qui va décrire successivement les couples solutions de ces \(n\) identités de Bézout en partant de la dernière. On pose initialement \((u,v):=(0,1)\). Pour obtenir le couple solution de la dernière identité, on vérifie facilement qu'il suffit d'appliquer la règle de réécriture \(R_{\color{#FF8}n}\) suivante :

Soit pour notre exemple \((u,v)\lf(1,0-2.1)=(1,-2)\) (cf. identité \((\ref{eq:box1})\)). Puis on recommence en appliquant successivement les règles \(R_{n-1}\), \(R_{n-2}\), etc. jusqu'à \(R_1\). En conclusion, l'algorithme d'Euclide étendu consiste dans un premier temps à appliquer l'algorithme d'Euclide aux entiers \(a\) et \(b\) pour construire la séquence des quotients \((q_i)_{i\in\llbracket 1,\,n\rrbracket }\) des divisions euclidiennes successives, puis dans un deuxième temps à appliquer les règles de réécritures \(R_{i}\) au couple \((u,v)\lf(0,1)\) pour \(i\) allant de \(n\) à \(1\).

Notons que la liste \(Q\) de l'algorithme ci-dessous contient tous les quotients, y compris le dernier pour lequel le reste est nul, la remontée se fait donc à partir de l'avant dernier quotient ici.

PGCD-Etendu(a,b)
ENTRÉE: deux entiers relatifs a, b
SORTIE: un couple d'entiers relatifs (u,v) tel que au+bv = PGCD(a,b)

Q ← []
TANT QUE (b > 0):
   t ← b
   Q ← Q + [a DIV b]
   b ← a MOD b
   a ← t
i ← #Q - 2
u ← 0
v ← 1
TANT QUE (i > 0):
   t ← u
   u ← v
   v ← t - Q[i] * v
   i ← i - 1
RENVOYER (u,v)

Le théorème suivant exprime la succession de réécritures \((\ref{eq:regle})\) en termes plus proche du langage ma­thé­ma­ti­que classique, à savoir un produit matriciel. L'annexe en fin de chapitre fournit le minimum vital sur les matrices pour comprendre l'énoncé de ce théorème.

Nous admettrons le théorème suivant dont nous avons donné les grandes lignes de la preuve. Cette fois, il s'agit d'un théorème constructif qui exprime d'une autre façon l'algorithme d'Euclide étendu.

Equation diophantienne \(ax+by=c\)

Les équations diophantiennes sont des équations polynomiales dont les inconnues sont cherchées dans \(\Z\) ou éventuellement \(\Q\). Elles jouent un rôle important en cryptologie.

Exemple : considérons l'équation à trois inconnues \begin{equation} \label{eq:Fermat} x^n+y^n=z^n. \end{equation} étudiée par Fermat*(*) Fermat était un ma­thé­ma­ti­cien et un ma­gis­trat fran­çais du 17ème siècle. admet une infinité de solutions dans \(\Z\) pour \(n=1\) puisqu'il simplement d'une addition. Pour \(n=2\), le triplet \((x,y,z):=(3,4,5)\) est une solution que les maçons connaissent par­fai­te­ment puisqu'elle leur permet de construire des murs à angles droits sans mètre ni équerre. En effet l'égalité \begin{equation} \label{eq:macon} 3^2+4^2=5^2 \end{equation} prouve qu'un triangle de côtés de longueurs \(3\) et \(4\) et d'hypothénuse \(5\) est nécessairement rectangle d'après la réciproque du théorème de Pythagore. Fermat conjectura en 1637 que l'équation \((\ref{eq:Fermat})\) n'ad­met­tait aucune solution dans \(\Z\) si \(n > 2\). Il a fallu attendre 1994 pour que le mathématicien anglais Andrew Wiles prouve enfin cette conjecture.

Nous serons moins ambitieux ici, et nous nous intéresserons à des équations à deux inconnues \(x\) et \(y\) de la forme

où \((a,b,c)\in\Z^3\) et où les solutions \((x,y)\) sont cherchées dans \(\Z\times\Z\). On reconnaît bien sûr la forme de l'identité de Bézout et on sait d'après le théorème de Bézout qu'il faut nécessairement que \((a,b)\mid c\) sans quoi il n'y a pas de solutions. Supposons donc que \((a,b)\mid c\). L'algorithme d'Euclide étendu nous fournit alors un couple \((u,v)\) solution de l'équation \begin{equation*} au+bv=(a,b) \end{equation*} Il suffit de multiplier cette équation par \(\frac{c}{(a,b)}\) pour obtenir \begin{equation} a\frac{c}{(a,b)}u+b\frac{c}{(a,b)}v=c. \end{equation} Et ainsi le couple \((x,y):=(\frac{c}{(a,b)}u,\frac{c}{(a,b)}v)\) est solution de l'équation \((\ref{eq:diolin})\).

Théorèmes de Gauss, Euler, Fermat

Nous avons vu que tous les éléments de \(\Z/n\Z\) n'étaient pas nécessairement inversibles. On peut donc se demander s'il existe un moyen de reconnaître ceux qui le sont sans avoir à calculer la table de multiplication. Tous les théorèmes qui vont suivre tournent autour de ces questions et du sous-ensemble \((\Z/n\Z)^\times\) des éléments inversibles de \(\Z/n\Z\) qui constitue un groupe multiplicatif.

Une première application du théorème de Gauss est de montrer que si \(p\) est un nombre premier, alors les coefficients binomiaux \(\binom{p}{k}\) sont tous divisibles par \(p\) pour \(k\in\ab{1}{p-1}\). En effet, on a \begin{equation*} \binom{p}{k}=\frac{p!}{k!(p-k)!}, \end{equation*} d'où \begin{equation*} p!={\color{#88F}k!(p-k)!\binom{p}{k}}, \end{equation*} mais puisque \(p\) divise \(p!\), il divise le membre droit de l'égalité ci-dessus. Mais \(p\) est premier avec \(h!(p-h)!\) pour tout \(k\in\ab{1}{p-1}\), le théorème de Gauss permet de conclure. Un corollaire important (le lemme d'Euclide) en découle immédiatement :

D'après ce théorème, on sait que le groupe \((\Z/n\Z)^\times\) des inversibles de \(\Z/n\Z\) est constitué des classes des entiers premiers avec \(n\). C'est un groupe fini, son ordre est donc le nombre d'entiers non-nuls inférieurs à \(n\) et premiers avec \(n\).

L'étude des propriétés du groupe multiplicatif \((\Z/n\Z)^{\times}\) est difficile, nous ne l'aborderons pas en première année en tant que tel, si ce n'est implicitement dans la dernière section. Notons simplement que dans le cas où \(n\) est premier, ce groupe est cyclique mais il n'est pas aisé de trouver des générateurs de ce groupe en général.

Le théorème des restes chinois

Que se passe-t-il si on mélange les congruences ? Une bande de \(17\) pirates possède un trésor en pièces d'or. Ils projettent de le partager et de donner le reste au cuisinier chinois qui recevrait \(3\) piè­ces. Au moment du partage, comme de bien entendu, les pirates se querellent et \(6\) sont tués. Un nou­veau partage donnerait \(4\) pièces au cuisinier. Mais l'affaire se gâte de nouveau car une tempête fait chavirer leur bâteau et il ne reste que 6 pirates et leur butin ainsi que le (chanceux) cuisinier qui re­ce­vrait alors 5 pièces d'or. Quel butin pourra récupérer le cuisinier s'il empoisonne les 6 autres sur­vi­vants ?

Si l'on note \(n\) la valeur du butin en nombre de pièces d'or, ce problème se traduit par le système de cong­gruen­ces suivant : \begin{equation} \label{eq:butin} \begin{cases} n\equiv 3\ (\text{mod}\ 17)\\ n\equiv 4\ (\text{mod}\ 11)\\ n\equiv 5\ (\text{mod}\ 6)\\ \end{cases} \end{equation}

On vérifie facilement que si l'on se donne une famille d'anneaux \((A_i)_{i\in I}\) et que l'on munit \(A\), l'en­semb­le produit des \(A_i\), des lois produits, alors \((A,+,\times)\) est un anneau, de surcroît commutatif si tous les \(A_i\) le sont. On l'appelle l'anneau produit des \(A_i\). Chacune des projections \(p_i\) est un mor­phis­me d'an­neaux surjectif.

Ici nous allons considérer une famille \((n_i)_{i\in\ab{1}{k}}\) de \(k\) entiers naturels non-nuls et premiers entre eux pour constituer la famille \((\Z/n_i\Z)_{i\in\ab{1}{k}}\) et l'anneau produit. Le théorème des restes chinois montre que cet anneau produit est isomorphe à l'anneau \(\Z/n\Z\) si \(n\) désigne le produit des \(n_i\), autrement dit on peut calculer indifféremment sur des entiers modulo \(n\) ou sur le \(k\)-uplet des restes modulo \(n_i\) de cet entier.

Si les entiers \(n_i\) ne sont pas premiers entre eux, il ne s'agit plus que d'une injection et un \(k\)-uplet \((r_i)_{i\in\ab{1}{k}}\) n'admet un antécédent que si \((n_i,n_j)\mid(r_i-r_j)\) pour tout couple \((i,j)\in\ab{1}{k}^2\).

Ce que nous cherchons quand nous voulons résoudre un système de congruences comme le problème du cuisinier chinois \((\ref{eq:butin})\) c'est l'isomorphisme réciproque \(\phi^{-1}\) de l'isomorphisme \(\phi\) pour calculer \(\phi^{-1}(3,4,5)\) et le théorème que nous venons d'établir ne fournit aucun moyen effectif de le calculer.

Notons \(\tilde{n_{i}}:=n/n_i\). Cet entier est premier avec \(n_i\) puisque les \(n_i\) sont premiers entre eux, il est donc inversible modulo \(n_i\) (cf. ce théorème). On calcule alors son inverse en appliquant l'algorithme d'Euclide étendu pour obtenir les deux coefficients \((u,v)\) de l'identité de Bézout :

et on réduit modulo \(n_i\) ce qui nous donne

donc \(u\) est l'inverse modulo \(n_i\) de \(\tilde{n_i}\), on le note \(\mu_i\). On définit alors l'entier

Il nous reste à vérifier que cet entier \(x\) est bien solution de l'équation \((\ref{eq:resteschinois})\). Si l'on calcule modulo \(n_i\) seul le terme \(\mu_i.\tilde{n_i}.r_i\) d'indice \(i\) est non-nul puisque tous les autres termes de cette somme sont des multiples de \(n_i\). Or \(\mu_i.\tilde{n_i}.r_i=r_i\) puisque \(\mu_i.\tilde{n_i}\equiv 1\ \text{mod}\ n_i\).

Nous allons enfin savoir quel est le montant de ce butin que va récupérer le cuisinier chinois… On ré­ca­pi­tu­le :

Il suffit d'utiliser le programme plus haut pour nous fournir les 3 couples \(({\color{#88F}u},v)\) de l'identité de Bézout pour les trois calculs de pgcd \(({\color{#F44}66},{\color{#FF8}17})\), \(({\color{#F44}102},{\color{#FF8}11})\) et \(({\color{#F44}187},{\color{#FF8}6})\) : \begin{align*} {\color{#F44}66}.{\color{#88F}8}+{\color{#FF8}17}.(-31)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_1}&={\color{#88F}8},\\ {\color{#F44}102}.{\color{#88F}4}+{\color{#FF8}11}.(-37)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_2}&={\color{#88F}4},\\ {\color{#F44}187}.{\color{#88F}1}+{\color{#FF8}6}.(-31)&\equiv 1\ (\text{mod}\ n) &\Rightarrow& & {\color{#88F}\mu_1}&={\color{#88F}1}. \end{align*} Et on peut calculer le butin \(x\) : \begin{align*} x&:={\color{#F44}66}.{\color{#88F}8}.3 + {\color{#F44}102}.{\color{#88F}4}.4 + {\color{#F44}187}{\color{#88F}1}.5\\ &= 4\,151,\\ &\equiv \boxed{785}\ (\text{mod}\ 1\,122). \end{align*}

Nous admettrons le corollaire suivant :

Le protocole RSA

Ils procèdent en trois phases, la première phase préparatoire étant réalisée une seule fois pour tous les chiffrements ultérieurs de Bob et déchiffrements d'Alice. Si Alice veut envoyer des messages à Bob, il faut qu'il effectue sa propre phase préparatoire et publie sa clé publique :

1. Phase préparatoire (Alice) :
   • Alice construit deux nombres premiers \(p\) et \(q\) calcule leur produit \(n:=p\,q\).
   • Alice choisit un entier \(e\) premier avec \(\varphi(n)=(p-1)(q-1).\)
   • Alice calcule \(d\), l'inverse de \(e\) modulo \(\varphi(n)\) : \begin{equation}\label{eq:inverses} e\,d\equiv 1\pmod{\varphi(n)}. \end{equation}
   • Alice divulgue alors sa clé publique \((n,\,e)\) et cache sa clé secrète \((p,\, q,\, d)\).
2. Chiffrement (Bob) :
   • Bob encode son message sous forme de nombre entier \(\color{lightblue}x\) tel que \(0\leq x < n.\)
   • Bob envoie à Alice le reste \(\color{orange}y\) de la division euclidienne de \(x^e\) par \(n\) : \begin{equation}\label{eq:encryption} {\color{orange}y}\equiv {\color{lightblue}x}^{e}\ (\text{mod}\ n). \end{equation}
3. Déchiffrement (Alice) :
   • Alice déchiffre le message en calculant \({\color{orange}y}^d\ (\text{mod}\ n)\). D'après l'équation (\ref{eq:inverses}), il existe un entier \(k\) tel que \(ed=1+k\,\varphi(n)\), donc
     \begin{align*} {\color{orange}y}^d&\equiv x^{ed}\ (\text{mod}\ n) \\ &\equiv x.x^{k\,\varphi(n)}\ (\text{mod}\ n)\\ &\equiv x.{\left(x^{\varphi(n)}\right)}^k\ (\text{mod}\ n)\\ &\equiv x.1^k\ (\text{mod}\ n)\quad\text{d'après (\ref{eq:ideuler})}\\ &\equiv {\color{lightblue}x}\ (\text{mod}\ n). \end{align*}

Ce protocole pose un grand nombre de problèmes algorithmiques. Le premier est de pouvoir réaliser des opérations avec des nombres entiers de plusieurs centaines de chiffres, une simple calculatrice ne peut évidemment pas le faire. Comment trouver des nombres premiers \(p\) et \(q\) aussi grands ? Comment calculer des puissances de nombres entiers aussi grandes ? Ce protocole est-il sûr ? Ces questions seront abordées en algorithmique et en cryptographie.

Malgré le développement d'algorithmes particulièrement efficaces, tous ces calculs restent malgré tout coûteux. Ce protocole est généralement utilisé, non pas pour chiffrer un message, mais pour transmettre une clef d'un protocole à clef secrète beaucoup moins gourmand en calculs. Ainsi Bob transmet une clef secrète \(k\) à Alice via le protocole à clef public rsa et tous les deux vont utiliser un autre protocole, à clef secrète cette fois, qui utilise la clef \(k\) pour chiffrer les messages.

Annexe : matrices

Pour ceux qui n'auraient pas encore rencontré de matrice \(\ell\times c\) où \((\ell,c)\in\N^2\), il s'agit en première approche d'une simple famille \(M\) d'éléments d'un anneau indexée par un produit d'intervalles \(\ab{1}{\ell}\times\ab{1}{c}\). Au lieu de représenter les éléments notés \(M_{(i,j)}\) ou encore \(M[i][j]\) de cette liste en séquence, on les représente dans une table de \(\ell\) lignes et \(c\) colonnes. La \(i\)-ème ligne contient la liste de tous les éléments de premier indice \(i\), la \(j\)-ème colonne contient la liste de tous les éléments de deuxième indice \(j\) (nous avons placé les indices en lieu et place des éléments de la matrice) : \begin{align*} M=\begin{pmatrix} (1,1) & (1,2) & \cdots & (1,{\color{#88F}j}) & \cdots & (1,c)\\ (2,1) & \cdots & & {\color{#88F}\vdots} & & (2,c) \\ (3,1) & \cdots& & {\color{#88F}\vdots} & & \vdots\\ \vdots & & & {\color{#88F}\vdots} & & \\ ({\color{#FF8}i},1) &{\color{#FF8}\cdots} &{\color{#FF8}\cdots} & ({\color{#FF8}i},{\color{#88F}j}) & {\color{#FF8}\cdots} & ({\color{#FF8}i},c)\\ \vdots & & & {\color{#88F}\vdots} & & \vdots \\ (\ell,1) &\cdots & & (\ell,{\color{#88F}j}) & \cdots & (\ell,c) \end{pmatrix} \end{align*}

La structure matricielle est plus pratique qu'une simple étagère de rangement, on peut ad­di­tion­ner et multiplier des ma­tri­ces et même multiplier des matrices par des nombres.

Pour l'addition c'est très simple, il faut que les matrices aient exactement le même nombre de lignes et de colonnes et il suffit d'additionner les \(\ell\times c\) éléments de chaque matrice terme-à-terme, par exemple : \begin{align*} \begin{pmatrix} 1&2\\ -5&1 \end{pmatrix} + \begin{pmatrix} -1&1\\ 2&3 \end{pmatrix} = \begin{pmatrix} 1-1&2+1\\ -5+2&1+3 \end{pmatrix} = \begin{pmatrix} 0&3\\ -3&4 \end{pmatrix} . \end{align*} Pour la multiplication, c'est plus compliqué car on peut multiplier des matrices \(G\) et \(D\) de di­men­sions différentes. On note \(\ell_g\) et \(c_g\) (resp. \(\ell_d\) et \(c_d\)) le nombre de lignes et de colonnes de la matrice \(G\) (resp. \(D\)). Il faut que \(c_g=\ell_d\) et la matrice résultat \(R:=G\times D\) contiendra \(\ell_g\) lignes et \(c_d\) colonnes. Le terme \(R[i][j]\) s'obtient en faisant le produit scalaire de la ligne \(i\) par la colonne \(j\), c'est-à-dire la somme des produits terme-à-terme des éléments de ces deux sous-listes dans le sens de lecture, par exemple \[(1,2,3).(2,-3,4)=1.2+2.(-3)+3.4=8.\]

Exemple : \begin{align*} \begin{pmatrix} \color{#88F}1&\color{#88F}0\\ -5&1\\ 2&-1 \end{pmatrix} \times \begin{pmatrix} -1&\color{#FF8}1\\ 2&\color{#FF8}3 \end{pmatrix} = \begin{pmatrix} (1,0).(-1,2) & {\color{#88F}(1,0)}.{\color{#FF8}(1,3)}\\ (-5,1).(-1,2) & (-5,1).(1,3)\\ (2,-1).(-1,2) & (2,-1).(1,3) \end{pmatrix} = \begin{pmatrix} -1&\boxed{1}\\ 7&-2\\ -4&-1 \end{pmatrix} . \end{align*} Le terme d'index \((\color{#88F}1,{\color{#FF8}2})\) de la matrice résultat est le produit scalaire de la ligne 1 de la matrice à gauche avec la colonne 2 de la matrice à droite. La multiplication d'une matrice \(M\) de dimension \(\ell\times c\) par un nombre fournit une matrice de même dimension dont chaque terme est le produit par ce nombre du terme correspondant de la matrice \(M\). Par exemple : \begin{equation*} (-2).\begin{pmatrix} 2 & 0\\ -1 & 4 \end{pmatrix} =\begin{pmatrix} -4 & 0\\ 2 & -8 \end{pmatrix}. \end{equation*} On a en particulier \begin{align*} \begin{pmatrix} a & b\\ c & d \end{pmatrix} \times \begin{pmatrix} a' & b'\\ c' & d' \end{pmatrix} &= \begin{pmatrix} aa'+bc' & ab'+bd'\\ ca'+dc' & cb'+dd' \end{pmatrix},\\ \begin{pmatrix} a & b\\ c & d \end{pmatrix} \times \begin{pmatrix} u\\ v \end{pmatrix} &= \begin{pmatrix} au+bv\\ cu+dv \end{pmatrix}. \end{align*}

Le cours d'algèbre linéaire de la deuxième année présentera ces notions calculatoire en détail.

Travaux pratiques

En séance

On rappelle que le quotient (resp. le reste) de la division euclidienne de \(a\) par \(b\) s'écrit a // b (resp. a % b) en Python.

def AfficheTable(T):
   for ligne in T:
      for x in ligne:
         print(str(x).rjust(3),end='')
      print()     

Compléments hors séance