Arithmétique

Introduction

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\).

L’arithmétique constitue l’un des socles les plus anciens des mathématiques, mais elle occupe également une place centrale en informatique, où elle intervient à tous les niveaux de la représentation et du traitement de l’information. Les entiers, leurs opérations et leurs propriétés structurent directement la manière dont les données sont codées, stockées et manipulées par les machines.

Dès les niveaux les plus élémentaires, les systèmes informatiques reposent sur une arithmétique discrète. La représentation binaire des entiers, les opérations sur les bits, ou encore les phénomènes de débordement correspondent à des formes implicites d’arithmétique modulaire. Les choix de codage des nombres — entiers signés, complément à deux, représentations flottantes — traduisent tous des contraintes arithmétiques fondamentales.

Au-delà de la représentation, l’arithmétique joue un rôle essentiel dans la conception d’algorithmes efficaces. Les méthodes de calcul rapide du plus grand commun diviseur, les algorithmes d’exponentiation modulaire ou les techniques de multiplication accélérée illustrent comment des propriétés élémentaires des entiers permettent de réduire drastiquement la complexité des calculs. La question n’est alors plus seulement de calculer, mais de calculer efficacement à grande échelle.

Ces notions deviennent particulièrement cruciales en cryptographie, où la sécurité des systèmes modernes repose sur des problèmes arithmétiques difficiles, comme la factorisation de grands entiers ou le calcul de logarithmes discrets. Des protocoles comme RSA ou Diffie–Hellman exploitent directement la structure des entiers modulo \(n\), rendant certaines opérations faciles dans un sens mais difficilement inversibles sans information secrète.

L’arithmétique intervient également dans la théorie des codes et des communications, où les corps finis permettent de détecter et corriger des erreurs dans les transmissions de données. Des opérations comme le XOR peuvent être interprétées comme une addition dans \(\mathbb{F}_2\), ce qui relie directement des mécanismes matériels simples à une structure algébrique abstraite.

Enfin, de nombreux domaines de l’informatique théorique mobilisent implicitement des raisonnements arithmétiques : périodicités dans les automates finis, comptage combinatoire, génération de nombres pseudo-aléatoires ou analyse de motifs. L’arithmétique apparaît ainsi comme un langage transversal, reliant la représentation des données, la conception d’algorithmes et l’étude de leur complexité.

Communication privée sur un canal public

Tout le monde, ou presque, a rencontré le chiffre de Jules César, l'empereur romain popularisé dans les bandes dessinées d'Astérix & Obélix. C'est certainement le système de chiffrement le plus simple, le plus connu, et le moins sûr.

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.

La quantité que seuls César et ses généraux connaissaient, est la valeur \(k\) du décalage circulaire des lettres. C'est la clé secrète de cet algorithme. Un tel algorithme 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, ne serait-ce que quelques lettres, il est en revanche inviolable si le message n'en contient qu'une.

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 clé. 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 clé \(k\) est la distance qui sépare \(E\) de cette lettre.

De nos jours, les systèmes de chiffrement à clé secrète employés dans les communications sont nettement plus robustes et bien plus complexes à cryptanalyser. Néanmoins, tous ont le même défaut, il faut partager la clé secrète avec les destinataires légitimes avant de leur transmettre des messages chiffrés. Si la transmission manuelle des clefs é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 clefs, une valise diplomatique par exemple. Mais dans ce cas pourquoi ne pas transmettre le message en clair via ce canal puisqu'il est sûr ?

Ces considérations liminaires nous amènent à nous intéresser au problème suivant :

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.

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éjà rencontré la relation de divisibilité définie sur l'ensemble des entiers naturels \(\N\). Cette relation se généralise à l'ensemble des entiers relatifs \(\Z\) :

Exemples. On a \(3\mid15\) ou encore \(-5\mid 15,\) mais \(3\not\mid 7\).

Cette relation binaire est réflexive, en effet \(a\,1=a\). Elle est également transitive puisque : \begin{align} \label{eq:k} a\mid b&\ \iff\ \exists k\in\Z\ \ a{\color{#88F}k}={\color{#AA0}b}\\ \label{eq:l} b\mid c&\ \iff\ \exists \ell\in\Z\ \ {\color{#AA0}b}{\color{#88F}\ell}=c \end{align} et donc \((a{\color{#88F}k)\ell}=a({\color{#88F}k\ell})=c\) en remplaçant \({\color{#AA0}b}\) par \(a{\color{#88F}k}\) dans \((\ref{eq:l}),\) ce qui prouve que \(a\mid c.\)

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\) non nul, on a \(n\mid(-n)\) et \((-n)\mid n\) et pourtant \(n\neq -n.\)

Nous avons déjà défini les nombres premiers dans le chapitre consacré à l'analyse combinatoire, mais leur rôle central en arithmétique justifie de rappeler leur définition ici.

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 l'ordre naturel défini sur \(\Z.\)

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.

Si l'on applique le théorème au couple \((a,b):=(8,3)\) on obtient le quotient \(q=2\) et le reste \(r=2\), mais pour le couple \((a,b):=(-8,3)\) on a le quotient \(q=-3\) et le reste \(r=1\).

divmod(8,3)
(2,2)
 >>> divmod(-8,3)
(-3,1)  

Revenons aux 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 : savant grec, ma­thé­ma­ti­cien, géo­gra­phe, ast­ro­no­me et poète. Il 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 principe de son crible est le suivant. On se donne un entier \(n\gt 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\gt 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\gt 1\), etc. jusqu'à ce que \(p^2\gt n\) :

ALGORITHME Crible(n): liste de booléens
DONNEES 
   n: entier
VARIABLES
   EstPremier[1:n]: booléens
   p, multp: entiers
DEBUT
   EstPremier[1] ← FAUX
   p ← 2
   TQ (p ≤ n) FAIRE
      EstPremier[i] ← VRAI
      p ← p + 1
   FTQ
   p ← 2
   TQ (p * p ≤ n) FAIRE
      SI (EstPremier[p]) ALORS
         multp ← p * p
         TQ (multp ≤ n) FAIRE
            EstPremier[multp] ← FAUX
            multp ← multp + p
         FTQ
      p ← p + 1
   FTQ
   RENVOYER EstPremier
FIN

Voici l'illustration de cet algorithme qui calque la méthode manuelle employée par Eratosthène en biffant les nombres entiers qui ne sont pas premiers dans une table.

Soit (\(k_i)_{i=1}^{\ell}\) 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 :

Le programme ci-dessous calcule cette décomposition pour un entier \(n \leqslant 1\,018\,080.\) C'est la plus grande valeur que l'on peut factoriser si l'on se contente de la liste des nombres premiers inférieurs à \(1\,000\) obtenue grâce à l'algorithme du crible d'Eratosthène : on calcule le reste de la division euclidienne de \(n\) par tous les nombres premiers \(2\leqslant p\leqslant \sqrt{n}\) (cf. exercice). On peut bien sûr aller plus loin, c'est la limite que nous nous sommes fixée pour illustrer le théorème ici.

Attention, la rapidité avec laquelle ce programme calcule 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 :

1. Combien y-en-a-t-il ?
2. Comment sont-ils répartis ?
3. Peut-on les calculer avec une formule ?
4. Est-il facile de déterminer si un nombre est premier ?
5. Est-il facile de construire un grand nombre premier ?
6. etc.

Congruences

Soit \(n\) un entier naturel. On note \(n\Z\) l'ensemble des multiples de \(n\) défini par \begin{equation} n\Z:=\{nz\mid z\in\Z\}. \end{equation}

C'est un sous-groupe du groupe additif \((\Z,+)\). En effet, \(0\) est un multiple de \(n\), la somme de deux multiples de \(n\) est un multiple de \(n\) et l'opposé d'un multiple de \(n\) est un multiple de \(n\) (cf. 2ème assertion du théorème de caractérisation des sous-groupes).

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\).

D'après la preuve du théorème précédent, les éléments de \(\Z/n\Z\) sont donc les images \(\overline{k}=\varphi_n(k)\) des \(n\) pre­miers entiers naturels. Souvent par abus de langage, on écrit que \(\Z/n\Z=\{0,1,2,\ldots,n-1\}\) en omettant la barre sur chaque entier qui signifie qu'il s'agit d'une classe d'équivalence. Cette confusion est sans danger précisément parce que la relation de congruence est compatible avec l'ad­di­tion. Autrement dit, quand on additionne deux classes d'équivalence pour la loi additive quotient, il suffit d'additionner les entiers correspondants et de calculer si nécessaire le reste de la division euclidienne par \(n\) pour retrouver un représentant dans l'ensemble \(\{0,1,2,\ldots,n-1\}\).

On construit donc facilement la table d'addition du groupe cyclique \(\Z/n\Z\) :

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 déjà vu au chapitre précédent.

Exemple. D'après le théorème de Lagrange, 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\).

Nous retrouverons le corollaire suivant plus loin, c'est le petit théorème de Fermat.

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 non seulement un anneau commutatif, mais aussi un corps puisque tout nombre réel non-nul admet un symétrique pour la multiplication.

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 :

L'anneau \(\Z\) est intègre puisqu'il n'a pas de diviseurs de 0 :

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 \((\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,+)\), les relations d'équivalence compatibles avec l'addition étant définies via les sous-groupes normaux exclusivement.

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 morphismes 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 suivante ?

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 de celle de \(\Z\).

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

On construit facilement la table de multiplication de \(\Z/n\Z\) :

Preuve par 9 et critères de divisibilité.

Nous venons de montrer que la surjection canonique \(\varphi_n:\Z\;\rg\;\Z/n\Z\), qui à un entier associe son reste modulo \(n\), est un morphisme d'anneaux. Nous allons exploiter ce résultat pour étudier l'algorithme de la preuve par 9, bien qu'il soit tombé en désuétude. Cet algorithme décide si le résultat d'une opération arithmétique sur des nombres entiers, produit, somme, etc. est juste ou non. C'est un algorithme probabiliste de Monte-Carlo : le temps de calcul est connu à l'avance, mais :

• Un résultat déclaré juste a une faible probabilité d'être faux.
• Un résultat déclaré faux est faux.

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_n(x+y)&=\varphi_n(x)+\varphi_n(y),\\ \varphi_n(xy)&=\varphi_n(x)\varphi_n(y). \end{align*}

Autrement dit, le reste de la division euclidienne par \(n\) d'une somme ou d'un produit doit être égal à la somme des restes ou le produit des restes modulo \(n\). 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é.

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 \(2305\) en base \(10\), ceci se traduit par \[ 2.10^{3}+3.10^{2}+0.10^1+5.10^0. \]

Plus généralement un entier \(x\) de \(k+1\) chiffres en base \(b\) s'écrit \[ \sum_{i=0}^k x_i\,b^i. \]

Par conséquent

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(x_i)= \begin{cases} x_i&\text{si}\ x_i\lt n.\\ {\color{green}0}&\text{si}\ x_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 \(x_i=n\) après l'addition : \begin{equation} \varphi_n(x)=\sum_{i=0}^k x_i. \end{equation}

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\) : \begin{align*} \varphi_{9}(121)+\varphi_{9}(41{\color{green}9}5)&=\varphi_{9}(4237)\\ (1+2+1)+(4+1+{\color{green}0}+5)&=(4+2+3+7)\\ 14&=16\\ {\color{red}5}&{\color{red}\;=7}\\ \end{align*}

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 et algorithme d'Euclide.

Plus grand commun diviseur

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 observé, \(0\) admet n'importe quel entier relatif comme diviseur, par conséquent si \(a=0\) et \(b=0\), l'ensemble des diviseurs commun de \(a\) et \(b\) est l'ensemble \(\Z\) qui n'admet pas de plus grand élément. On convient alors de poser la convention \((0,0):=0\).

Algorithme d'Euclide

Malheureusement, la décomposition d'un entier en produit de fac­teurs premiers à l'aide de divisions euclidiennes est particulièrement coûteuse, nous ne l'avons pro­gram­mée ici que pour des valeurs de \(a\) et \(b\) très petites.

def factoriser(n):
    p = 2
    PREMIERS = ()
    while (p*p <= n):
        while (n % p == 0):
            PREMIERS += (p,)
            n = n // p
        p = 3 if (p == 2) else p + 2
    if (n > 1):
        PREMIERS += (n,)
    return(PREMIERS)

n = int(input("n = "))
print(factoriser(n))

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, c'est 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 euclidienne fournit le résultat.

def PGCD(a,b):
   while (b > 0):
      (a, b) = (b, a % b)
   return a

Si \(a\lt 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.

Le programme ci-dessous permet d'observer la trace de cet algorithme pour des valeurs arbitraires de \(a\) et \(b.\) Sa version dite étendue étudiée plus loin permettra de calculer un couple \((u,v)\) solution de l'équation \(au+bv=(a,b)\) (identité de Bézout) que nous fournissons dès à présent.

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.

ALGORITHME PGCD-Etendu(a,b): (u,v)
DONNEES: 
   a,b: entiers relatifs
VARIABLES
   Q: liste d'entiers relatifs
   t,u,v: entiers relatifs
DEBUT
   Q ← []
   TQ (b > 0) FAIRE
       t ← b
       Q ← Q + [a DIV b]
       b ← a MOD b
       a ← t
   FTQ
   i ← #Q - 2
   (u,v) ← (0,1)
   TQ (i > 0) FAIRE
      t ← u
      u ← v
      v ← t - Q[i] * v
      i ← i - 1
   FTQ
   RENVOYER (u,v)
FIN

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.

Équation diophantienne ax +by = c

Les équations diophantiennes^#Diophante était un mathématicien grec qui vécut entre le 1er et le 4ème siècle de notre ère et fut l'un des pionniers de l'algè­bre. 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*Pierre de Fermat était un ma­thé­ma­ti­cien et ma­gis­trat fran­çais du 17ème siècle.. Elle admet une infinité de solutions dans \(\Z^3\) pour \(n=1\) puisque pour tout couple \((x,y)\) la valeur \(z:=x+y\) convient. 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\gt 2\). Il a fallu attendre 1994 pour que le mathématicien anglais Andrew Wiles prouve enfin cette conjecture.

Nous sommes moins ambitieux ici, et nous nous contentons d'é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})\).

Gauss, Euclide, Euler, Fermat et restes chinois

Théorèmes de Gauss, Euler, Fermat

Nous avons vu que d'autres entiers que \(0\) pouvaient ne pas admettre d'inverse dans \(\Z/n\Z\). On peut alors se demander s'il existe un moyen de trouver quels sont les entiers modulo \(n\) qui admettent un inverse sans calculer la table de multiplication.

Tous les théorèmes qui vont suivre tournent autour des questions de divisibilité. C'est le sous-ensemble \((\Z/n\Z)^\times\) des éléments inversibles de \(\Z/n\Z\) qui est au centre de ce qui suit. Cet ensemble forme un groupe quand on le munit de la multiplication.

Une première application du lemme de Gauss*Carl Friedrich Gauss : mathématicien, astronome et physicien allemand du 18ème siècle. Ses con­tri­bu­tions majeures font de lui l'un des plus bril­lants scien­ti­fi­ques de tous les temps. 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 lemme 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\) qui définit une fonction*Leonhard Euler était un éminent mathématicien et physicien Suisse du 18ème siècle. :

On en déduit immédiatement le corollaire suivant, mais il peut être démontré comme un résultat autonome de plusieurs façons :

Le théorème des restes chinois

Que se passe-t-il si l'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 les \(3\) piè­ces restantes au cuisinier chinois. Au moment du partage, comme de bien entendu, les pirates se querellent et \(6\) sont tués. Un nou­veau partage prévoit de donnerles \(4\) pièces restantes au cuisinier, mais l'affaire se gâte de nouveau car une tempête a fait chavirer leur navire. Cette fois, il ne reste que \(6\) pirates plus le cuisinier, qui re­ce­vrait les 5 pièces d'or restantes une fois partagé entre les pirates.

Quel butin pourrait récupérer le cuisinier s'il empoisonnait ces 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 similaire à celui des restes chinois \((\ref{eq:butin})\), c'est l'isomorphisme réciproque \(\phi^{-1}\) de l'isomorphisme \(\phi\) pour calculer \(\phi^{-1}(3,4,5)\). Malheureusement, 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 :

En réduisant modulo \(n_i\), on obtient

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

Le protocole RSA est une application extrêmement ingénieuse du théorème d'Euler pour communiquer des messages chiffrés entre deux entités \(A\) et \(B\) (Alice et Bob dans le folklore cryptographique), sans qu'elles aient jamais à communiquer de quantité secrète entre elles. Autrement dit, elles peuvent utiliser ce protocole sur un canal public et aucune des informations qu'elles feront transiter ne pourra servir à retrouver le contenu réel des messages qu'elles transmettent (au prix de quelques précautions mathématiques à considérer).

Le protocole est asymétrique car il est unidirectionnel, nous le présentons ici pour une communication \(\text{Bob}\to\text{Alice}.\) Le gros du travail mathématique est réalisé une seule fois en amont par Alice, avant que Bob ne puisse lui envoyer les messages qu'il souhaite. Bien sûr, pour qu'Aline puisse elle aussi communiquer avec Bob, un travail préparatoire similaire devra être réalisé par Bob, une fois pour toutes là aussi.

Tout se déroule dans deux anneaux quotients \(\Z/n\Z\) et \(\Z/\phi(n)\Z\) pour un entier \(n\) déterminé par Alice dans la phase préparatoire. Le simulateur ci-dessous décompose les trois phases suivies par les deux protagonistes. Les valeurs sur fond vert sont publiques, celles sur fond rouge restent secrètes :

La phase préparatoire n'est effectuée qu'une seule fois pour tous les chiffrements ultérieurs de Bob et tous les déchiffrements d'Alice, c'est la plus complexe. Les deux autres se font ensuite très simplement si l'on dispose d'un langage évolué comme le Python 3. Le travail de Bob se limite à écrire

y = x**e % n

puis Alice déchiffre avec

x = y**d % n

Il faut réaliser que cette facilité d'écriture accordée par le langage Python cache en fait des algorithmes sophistiqués. Ils seront étudiés en algorithmique.

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 clé d'un protocole à clé secrète beaucoup moins gourmand en calculs. Ainsi Bob transmet une clé secrète \(k\) à Alice via le protocole à clé public rsa et tous les deux vont utiliser un autre protocole, à clé secrète cette fois, qui utilise la clé \(k\) pour chiffrer les messages.

Annexe : matrices

Le calcul matriciel désigne l'ensemble des techniques de calcul pour réaliser les opérations usuelles sur les applications linéaires définies sur des espaces vectoriels de dimensions finies, donc des morphismes.

Pour ceux qui n'auraient pas encore rencontré de matrice \(\ell\times c\) à \(\ell\) lignes et \(c\) colonnes où \((\ell,c)\in\N^2\), il s'agit en première approche d'une étagère à casiers pour ranger les éléments d'un anneau \(A\). Plus formellement, c'est une famille \(M\) d'éléments d'un anneau \(A\) indexée par un produit d'intervalles \(\ab{1}{\ell}\times\ab{1}{c}\). On représente les éléments de cette matrice sous forme de table constituée 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). La valeur dans le casier \(({\color{#F84}i},{\color{#48F}j})\) est désignée par \(M[i,j]\) ou \(M[i][j]\) ou encore \(M_{i,j}\) selon les auteurs et/ou le contexte.

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, grâce aux lois de composition de l'anneau \(A\).

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 un peu 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)\cdot(2,-3,4)=1\cdot2+2\cdot(-3)+3\cdot 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)\cdot(-1,2) & {\color{#88F}(1,0)}\cdot{\color{#FF8}(1,3)}\\ (-5,1)\cdot(-1,2) & (-5,1)\cdot(1,3)\\ (2,-1)\cdot(-1,2) & (2,-1)\cdot(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)\cdot\begin{pmatrix} 2 & 0\\ -1 & 4 \end{pmatrix} =\begin{pmatrix} (-2)\cdot 2 & (-2)\cdot 0\\ (-2)\cdot (-1) & (-2)\cdot 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 deuxième année présentera ces notions calculatoires en détail.

Factoriser(60)
2.2.3.5

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