Anneau Z/nZ et RSA en L2 de maths : cours et méthodes
Ce cours sur l’anneau Z/nZ L2 part des anneaux, corps et idéaux pour construire pas à pas l’arithmétique modulaire. Nous définissons la congruence comme une relation d’équivalence, puis nous fabriquons Z/nZ par passage au quotient, en vérifiant que les opérations sont bien définies.
Ensuite, le chapitre caractérise les classes inversibles, montre que Z/pZ est un corps et calcule les inverses par l’algorithme d’Euclide étendu. Il démontre les théorèmes d’Euler et de Fermat, le théorème chinois et le critère d’Euler sur les carrés de F_p.
Enfin, tout converge vers le chiffrement RSA, dont nous prouvons le fonctionnement sur un exemple complet. Ce chapitre du semestre 3 prépare l’étude des groupes, des polynômes sur un corps fini et de la cryptographie.
Ce que vous saurez faire
- Reconnaître un anneau, un corps ou un idéal, et décrire tous les idéaux de \(\mathbb{Z}\).
- Construire \(\mathbb{Z}/n\mathbb{Z}\) comme ensemble quotient et y calculer sans erreur.
- Décider si une classe est inversible et calculer son inverse par l’algorithme d’Euclide étendu.
- Réduire une grande puissance modulo \(n\) grâce aux théorèmes de Fermat et d’Euler.
- Résoudre un système de congruences par le théorème chinois.
- Reconnaître les carrés de \(\mathbb{F}_p\) avec le critère d’Euler.
- Fabriquer des clés RSA, chiffrer, déchiffrer, et justifier que le procédé fonctionne.
1. Anneaux, corps et idéaux
Les entiers, les polynômes et les matrices carrées partagent une même structure : on peut y additionner et y multiplier avec les règles usuelles. Nous dégageons ici le cadre commun, appelé anneau. Ensuite, nous verrons que \(\mathbb{Z}/n\mathbb{Z}\) en est un exemple central.
1.1 Anneaux et corps
On se donne un ensemble \(A\), une addition \(+\) et une multiplication \(\times\) sur \(A\). Le triplet \((A,+,\times)\) est un anneau lorsque :
- \((A,+)\) est un groupe commutatif, de neutre noté \(0_A\) ;
- la loi \(\times\) est associative et possède un neutre \(1_A\) ;
- \(\times\) est distributive à gauche et à droite sur \(+\).
L’anneau est commutatif si \(\times\) l’est. Un élément \(a\) est inversible s’il existe \(b\) tel que \(ab=ba=1_A\). L’ensemble des inversibles se note \(A^{\times}\).
On appelle corps un anneau commutatif \(K\), non réduit à \(\{0_K\}\), tel que \(K^{\times}=K\setminus\{0_K\}\). Un anneau commutatif est intègre si \(1_A\neq 0_A\) et si \(ab=0_A\) entraîne \(a=0_A\) ou \(b=0_A\).
Par exemple, \(\mathbb{Q}\), \(\mathbb{R}\) et \(\mathbb{C}\) sont des corps. En revanche, \(\mathbb{Z}\) est un anneau intègre qui n’est pas un corps : ses seuls inversibles sont \(1\) et \(-1\). De même, \(\mathbb{R}[X]\) est intègre, d’inversibles les constantes non nulles. Enfin, l’anneau des matrices réelles carrées d’ordre \(3\) n’est ni commutatif, ni intègre.
Tout corps est intègre. En effet, si \(ab=0\) et \(a\neq 0\), on multiplie par \(a^{-1}\) et l’on obtient \(b=0\).
1.2 Idéaux d’un anneau commutatif
Dans \(\mathbb{Z}\), l’ensemble des multiples de \(6\) est stable par somme. De plus, il « absorbe » les produits : un multiple de \(6\) fois un entier quelconque reste un multiple de \(6\). Cette propriété d’absorption définit les idéaux.
Soit \(A\) un anneau commutatif. Une partie \(I\) de \(A\) est un idéal si \((I,+)\) est un sous-groupe de \((A,+)\) et si, pour tous \(x\in I\) et \(a\in A\), on a \(ax\in I\). Pour \(x\in A\), l’ensemble \(xA=\{xa\ :\ a\in A\}\) est un idéal, appelé idéal engendré par \(x\).
Piège à éviter :
Un idéal n’est presque jamais un sous-anneau. En effet, si un idéal \(I\) contient \(1_A\), alors il contient \(a\times 1_A=a\) pour tout \(a\), donc \(I=A\). Plus généralement, un idéal qui contient un inversible est l’anneau entier.
Les idéaux de \(\mathbb{Z}\) sont exactement les ensembles \(n\mathbb{Z}\), avec \(n\in\mathbb{N}\). L’entier \(n\) est alors unique.
Chaque \(n\mathbb{Z}\) est un idéal. Pour la réciproque, partons d’un idéal \(I\) de \(\mathbb{Z}\). Le cas \(I=\{0\}=0\mathbb{Z}\) est clair. Dans l’autre cas, \(I\) possède un élément \(y\neq 0\), et \(|y|\) est aussi dans \(I\), puisque \(-y\in I\). L’ensemble des éléments strictement positifs de \(I\) est donc non vide ; son minimum est noté \(n\). Par absorption, \(I\) contient tous les multiples de \(n\). Prenons maintenant \(x\) quelconque dans \(I\), et écrivons \(x=nq+r\), avec \(0\leq r<n\). Le reste \(r\) s’écrit \(x+(-q)n\) : c’est un élément de \(I\) plus petit que \(n\). Il est donc nul, ce qui donne \(x\in n\mathbb{Z}\). Ainsi, \(I=n\mathbb{Z}\). L’unicité vient de ce que \(n\) est le plus petit élément positif de \(n\mathbb{Z}\).
Soient \(a\) et \(b\) deux entiers. La somme \(a\mathbb{Z}+b\mathbb{Z}\) est un idéal de \(\mathbb{Z}\) : son générateur positif est le pgcd \(a\wedge b\). De même, l’intersection des deux idéaux a pour générateur positif le ppcm de \(a\) et \(b\). En particulier, il existe \(u\) et \(v\) entiers tels que \(au+bv=a\wedge b\) : c’est la relation de Bézout.
2. Congruences et construction de l’anneau Z/nZ
2.1 Une relation d’équivalence
Fixons un entier \(n\geq 2\). Deux entiers ont le même reste dans la division par \(n\) exactement lorsque leur différence est un multiple de \(n\). Nous transformons cette remarque en relation.
On dit que \(a\) est congru à \(b\) modulo \(n\), et l’on écrit \(a\equiv b\ [n]\), lorsque \(a-b\in n\mathbb{Z}\).
La congruence modulo \(n\) est une relation d’équivalence sur \(\mathbb{Z}\). De plus, elle est compatible avec les opérations : si \(a\equiv a^{\prime}\ [n]\) et \(b\equiv b^{\prime}\ [n]\), alors \(a+b\equiv a^{\prime}+b^{\prime}\ [n]\) et \(ab\equiv a^{\prime}b^{\prime}\ [n]\).
La réflexivité vient de \(0\in n\mathbb{Z}\), la symétrie de la stabilité de \(n\mathbb{Z}\) par opposé, et la transitivité de sa stabilité par somme. Pour le produit, on écrit
\[ab-a^{\prime}b^{\prime}=a(b-b^{\prime})+b^{\prime}(a-a^{\prime}).\]
Les deux termes sont dans \(n\mathbb{Z}\) par absorption, donc leur somme aussi. La somme se traite de la même façon.
2.2 L’ensemble quotient et ses opérations
La classe de \(a\) modulo \(n\) est \(\overline{a}=a+n\mathbb{Z}=\{a+kn\ :\ k\in\mathbb{Z}\}\). L’ensemble quotient \(\mathbb{Z}/n\mathbb{Z}\) est l’ensemble de ces classes. Par division euclidienne, chaque classe contient un unique représentant dans \(\{0,\dots,n-1\}\). Ainsi, \(\mathbb{Z}/n\mathbb{Z}=\{\overline{0},\overline{1},\dots,\overline{n-1}\}\) possède exactement \(n\) éléments.
Pour additionner deux classes, l’idée naturelle est d’additionner des représentants : \(\overline{x}+\overline{y}\) devrait valoir \(\overline{x+y}\), et de même pour le produit. Cependant, une classe a une infinité de représentants. Il faut donc vérifier que le résultat ne dépend pas du représentant choisi. C’est exactement ce qu’affirme la compatibilité démontrée plus haut.
Avec l’addition et la multiplication des représentants, l’ensemble \(\mathbb{Z}/n\mathbb{Z}\) est un anneau commutatif, de neutres \(\overline{0}\) et \(\overline{1}\). L’application \(a\mapsto\overline{a}\) de \(\mathbb{Z}\) dans \(\mathbb{Z}/n\mathbb{Z}\) est un morphisme d’anneaux surjectif, de noyau \(n\mathbb{Z}\).
Chaque axiome se transfère depuis \(\mathbb{Z}\). Par exemple, \(\overline{a}(\overline{b}+\overline{c})=\overline{a(b+c)}=\overline{ab+ac}=\overline{a}\,\overline{b}+\overline{a}\,\overline{c}\). On visualise souvent \(\mathbb{Z}/12\mathbb{Z}\) comme le cadran d’une horloge : ajouter \(\overline{1}\) revient à avancer d’une heure.
Calculons dans \(\mathbb{Z}/12\mathbb{Z}\). D’abord, \(\overline{7}+\overline{8}=\overline{15}=\overline{3}\), comme sur l’horloge. Ensuite, \(\overline{7}\times\overline{8}=\overline{56}=\overline{8}\), car \(56=4\times 12+8\). De plus, \(\overline{5}^2=\overline{25}=\overline{1}\) : la classe \(\overline{5}\) est son propre inverse. En revanche, \(\overline{4}\times\overline{3}=\overline{0}\), alors que ni \(\overline{4}\) ni \(\overline{3}\) n’est nulle. L’anneau \(\mathbb{Z}/12\mathbb{Z}\) n’est donc pas intègre.
- Remplacer chaque entier par un représentant petit, éventuellement négatif : \(\overline{11}=\overline{-1}\) dans \(\mathbb{Z}/12\mathbb{Z}\).
- Réduire après chaque produit, pour garder des nombres de taille modeste.
- Pour une puissance \(\overline{a}^k\), chercher une petite puissance égale à \(\overline{1}\) ou \(\overline{-1}\), puis diviser \(k\) par son exposant.
Par exemple, dans \(\mathbb{Z}/12\mathbb{Z}\), on a \(\overline{11}^{2027}=\overline{-1}^{2027}=\overline{-1}=\overline{11}\), sans aucun calcul lourd.
3. Inversibles de Z/nZ et corps Z/pZ
3.1 Le critère d’inversibilité
Soit \(a\in\mathbb{Z}\). La classe \(\overline{a}\) est inversible dans \(\mathbb{Z}/n\mathbb{Z}\) si et seulement si \(a\wedge n=1\).
Supposons \(\overline{a}\,\overline{u}=\overline{1}\). Il existe alors \(k\in\mathbb{Z}\) tel que \(au=1+kn\), soit \(au-kn=1\). Tout diviseur commun de \(a\) et \(n\) divise donc \(1\) : ainsi, \(a\wedge n=1\). Réciproquement, si \(a\wedge n=1\), la relation de Bézout fournit \(u\) et \(v\) tels que \(au+nv=1\). Comme \(n\) est nul dans \(\mathbb{Z}/n\mathbb{Z}\), le terme \(nv\) disparaît lorsqu’on prend les classes. Il reste \(\overline{a}\,\overline{u}=\overline{1}\).
La preuve est constructive : l’inverse de \(\overline{a}\) est la classe du coefficient \(u\) de Bézout. On obtient \(u\) en remontant l’algorithme d’Euclide.
- Effectuer les divisions euclidiennes successives de \(n\) par \(a\), puis du diviseur par le reste, jusqu’au reste \(1\).
- Exprimer ce reste \(1\) à partir de la dernière division, puis remplacer chaque reste par son expression, en remontant.
- Lire une égalité \(au+nv=1\) ; l’inverse est \(\overline{u}\), que l’on ramène entre \(0\) et \(n-1\).
- Vérifier en calculant \(au\) modulo \(n\).
Inversons \(\overline{23}\) dans \(\mathbb{Z}/80\mathbb{Z}\). On a \(80=3\times 23+11\), puis \(23=2\times 11+1\). En remontant, \(1=23-2\times 11=23-2(80-3\times 23)=7\times 23-2\times 80\). Par conséquent, \(\overline{23}^{-1}=\overline{7}\). Vérification : \(23\times 7=161=2\times 80+1\).
3.2 Quand Z/nZ est-il un corps ?
Les propriétés suivantes sont équivalentes : \(n\) est premier ; \(\mathbb{Z}/n\mathbb{Z}\) est un corps ; \(\mathbb{Z}/n\mathbb{Z}\) est intègre. Pour \(p\) premier, ce corps à \(p\) éléments est noté \(\mathbb{F}_p\).
Si \(n\) est premier, tout \(a\) non multiple de \(n\) vérifie \(a\wedge n=1\) : chaque classe non nulle est inversible. Ensuite, un corps est toujours intègre. Enfin, si \(n=rs\) avec \(1<r,s<n\), alors \(\overline{r}\,\overline{s}=\overline{0}\) avec deux facteurs non nuls : l’anneau n’est pas intègre.
Dans \(\mathbb{Z}/12\mathbb{Z}\), on ne peut pas simplifier : \(\overline{4}\times\overline{2}=\overline{4}\times\overline{5}=\overline{8}\), mais \(\overline{2}\neq\overline{5}\). La simplification par \(\overline{a}\) n’est permise que si \(\overline{a}\) est inversible. De même, l’équation \(\overline{x}^2=\overline{1}\) y possède quatre solutions : \(\overline{1}\), \(\overline{5}\), \(\overline{7}\) et \(\overline{11}\). Dans un corps, elle n’en aurait que deux.
Piège à éviter :
Dans \(\mathbb{Z}/n\mathbb{Z}\), la notation \(\frac{1}{3}\) n’a de sens que si \(\overline{3}\) est inversible. Par exemple, dans \(\mathbb{Z}/10\mathbb{Z}\), on a \(\overline{3}^{-1}=\overline{7}\), qui n’a rien à voir avec le réel \(0{,}333\dots\). En revanche, \(\overline{5}\) n’y est pas inversible.
4. Indicatrice d’Euler et théorème d’Euler
4.1 Compter les inversibles
L’indicatrice d’Euler de \(n\geq 1\) est le nombre \(\varphi(n)\) d’entiers \(k\in\{1,\dots,n\}\) premiers avec \(n\). D’après le paragraphe 3, c’est aussi le cardinal du groupe \((\mathbb{Z}/n\mathbb{Z})^{\times}\).
Pour \(p\) premier et \(k\geq 1\), \(\varphi(p^k)=p^k-p^{k-1}\). Si \(m\wedge n=1\), alors \(\varphi(mn)=\varphi(m)\varphi(n)\). Par conséquent, si \(n=p_1^{k_1}\cdots p_r^{k_r}\), on a
\[\varphi(n)=n\prod_{i=1}^{r}\left(1-\frac{1}{p_i}\right).\]
Le premier point se prouve en retirant les \(p^{k-1}\) multiples de \(p\). Le second découle du théorème chinois, démontré au paragraphe 5. Par exemple, \(\varphi(60)=60\times\frac{1}{2}\times\frac{2}{3}\times\frac{4}{5}=16\). La figure montre que \(\varphi(n)\) vaut \(n-1\) exactement lorsque \(n\) est premier.
4.2 Les théorèmes d’Euler et de Fermat
Si \(a\wedge n=1\), alors \(a^{\varphi(n)}\equiv 1\ [n]\). En particulier, pour \(p\) premier ne divisant pas \(a\), on a \(a^{p-1}\equiv 1\ [p]\) : c’est le petit théorème de Fermat.
Les inversibles de \(\mathbb{Z}/n\mathbb{Z}\) sont au nombre de \(r=\varphi(n)\) ; notons-les \(x_1,\dots,x_r\). Comme \(\overline{a}\) est inversible, la multiplication par \(\overline{a}\) envoie un inversible sur un inversible, et elle est bijective, de réciproque \(x\mapsto\overline{a}^{-1}x\). Les produits \(\overline{a}x_1,\dots,\overline{a}x_r\) sont donc les \(x_i\) dans un autre ordre. En multipliant tout, on obtient \(\overline{a}^{\,r}x_1\cdots x_r=x_1\cdots x_r\). Enfin, le produit \(x_1\cdots x_r\) est inversible : on peut simplifier, d’où \(\overline{a}^{\,r}=\overline{1}\).
Calculons le reste de \(3^{50}\) modulo \(20\). D’abord, \(3\wedge 20=1\) et \(\varphi(20)=20\times\frac{1}{2}\times\frac{4}{5}=8\). Ensuite, \(50=6\times 8+2\). Par le théorème d’Euler, \(3^{50}=(3^8)^6\times 3^2\equiv 9\ [20]\). Le reste cherché est donc \(9\).
Remarque :
L’exposant \(\varphi(n)\) n’est pas toujours le plus petit possible. Par exemple, \(3^4=81\equiv 1\ [20]\) alors que \(\varphi(20)=8\). Cependant, le plus petit exposant convenable divise toujours \(\varphi(n)\), ce que le chapitre sur les groupes expliquera avec le théorème de Lagrange.
5. Le théorème chinois
Connaître le reste d’un entier modulo \(4\) et modulo \(9\) permet-il de connaître son reste modulo \(36\) ? La réponse est oui, car \(4\) et \(9\) sont premiers entre eux. C’est le contenu du théorème chinois.
Soient \(m\) et \(n\) deux entiers supérieurs ou égaux à \(2\), premiers entre eux. L’application
\[\psi\ :\ \mathbb{Z}/mn\mathbb{Z}\to\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z},\qquad x+mn\mathbb{Z}\mapsto(x+m\mathbb{Z},\ x+n\mathbb{Z})\]
ne dépend pas du représentant \(x\) choisi. De plus, elle respecte les deux lois et l’unité, et elle est bijective. Ainsi, \(\psi\) réalise un isomorphisme d’anneaux.
D’abord, si \(x\equiv y\ [mn]\), alors \(x\equiv y\) modulo \(m\) et modulo \(n\) : l’application est bien définie. Ensuite, elle respecte la somme, le produit et l’unité, car on calcule composante par composante. Montrons qu’elle est injective. Si \(\psi(\overline{x})=(\overline{0},\overline{0})\), alors \(m\) et \(n\) divisent \(x\). Comme \(m\wedge n=1\), le lemme de Gauss donne \(mn\mid x\), donc \(\overline{x}=\overline{0}\). Enfin, les deux ensembles ont \(mn\) éléments : l’application injective \(\psi\) est donc bijective.
La figure place chaque entier de \(0\) à \(19\) dans la case repérée par ses restes modulo \(4\) et modulo \(5\). Chaque case reçoit exactement un entier : c’est la bijectivité de \(\psi\).
L’isomorphisme \(\psi\) envoie les inversibles sur les couples d’inversibles. Par conséquent, \(\varphi(mn)=\varphi(m)\varphi(n)\) lorsque \(m\wedge n=1\).
- Vérifier que les modules sont premiers entre eux deux à deux.
- Trouver une relation de Bézout \(mu+nv=1\).
- Poser \(e_1=nv\), qui vaut \(1\) modulo \(m\) et \(0\) modulo \(n\), et \(e_2=mu\), qui vaut \(0\) modulo \(m\) et \(1\) modulo \(n\).
- La solution de \(x\equiv a\ [m]\), \(x\equiv b\ [n]\) est \(x\equiv ae_1+be_2\ [mn]\). Vérifier les deux congruences.
Résolvons \(x\equiv 1\ [4]\) et \(x\equiv 4\ [9]\). On a \(4\times(-2)+9\times 1=1\). Ainsi, \(e_1=9\) et \(e_2=-8\equiv 28\ [36]\). Ensuite, \(x\equiv 1\times 9+4\times 28=121\equiv 13\ [36]\). Vérification : \(13=3\times 4+1\) et \(13=9+4\). Les solutions sont donc les entiers \(13+36k\), \(k\in\mathbb{Z}\).
Piège à éviter :
Si les modules ne sont pas premiers entre eux, le théorème tombe. Par exemple, \(x\equiv 0\ [4]\) et \(x\equiv 1\ [6]\) n’a aucune solution, car la première impose \(x\) pair et la seconde \(x\) impair. On vérifie toujours la compatibilité modulo le pgcd des modules.
6. Les carrés dans le corps F_p
Dans ce paragraphe, \(p\) est un nombre premier impair. Nous cherchons quelles classes non nulles de \(\mathbb{F}_p\) sont des carrés. Cette question prépare les tests de primalité et la résolution d’équations du second degré modulo \(p\).
Le corps \(\mathbb{F}_p\) contient exactement \(\frac{p-1}{2}\) carrés non nuls.
Considérons \(s\ :\ x\mapsto x^2\) sur \(\mathbb{F}_p^{\times}\). Si \(x^2=y^2\), alors \((x-y)(x+y)=0\). Comme \(\mathbb{F}_p\) est intègre, on obtient \(y=x\) ou \(y=-x\). De plus, \(x\neq -x\), car \(2x=0\) imposerait \(x=0\) quand \(p\) est impair. Chaque carré non nul a donc exactement deux antécédents. Ainsi, l’image de \(s\) a \(\frac{p-1}{2}\) éléments.
Critère d’Euler. Pour \(a\in\mathbb{F}_p^{\times}\), on a \(a^{\frac{p-1}{2}}=1\) si \(a\) est un carré, et \(a^{\frac{p-1}{2}}=-1\) sinon.
Si \(a=x^2\), alors \(a^{\frac{p-1}{2}}=x^{p-1}=1\) par Fermat. Les \(\frac{p-1}{2}\) carrés sont donc racines du polynôme \(X^{\frac{p-1}{2}}-1\). Comme \(\mathbb{F}_p\) est un corps, le nombre de racines de ce polynôme ne dépasse pas son degré. Les carrés remplissent déjà toutes les places : ce sont toutes les racines. Si \(a\) n’est pas un carré, posons \(b=a^{\frac{p-1}{2}}\). Alors \(b^2=a^{p-1}=1\), donc \(b=\pm 1\). Comme \(b\neq 1\), on conclut \(b=-1\).
La classe \(-1\) est un carré de \(\mathbb{F}_p\) si et seulement si \(p\equiv 1\ [4]\).
En effet, \((-1)^{\frac{p-1}{2}}\) vaut \(1\) exactement lorsque \(\frac{p-1}{2}\) est pair. Prenons \(p=13\). Les carrés non nuls sont \(1\), \(4\), \(9\), \(3\), \(12\) et \(10\), soit six classes. On retrouve bien \(12=-1\), avec \(5^2=25\equiv -1\ [13]\). En revanche, \(2^6=64\equiv -1\ [13]\) : la classe \(2\) n’est pas un carré.
7. Le chiffrement RSA
Le système RSA, publié en 1977, permet à quiconque de chiffrer un message pour Bob, alors que seul Bob peut le déchiffrer. Sa sécurité repose sur une asymétrie : multiplier deux grands nombres premiers est facile, mais retrouver ces facteurs à partir du produit semble très difficile. Tout le reste n’est que de l’arithmétique dans \(\mathbb{Z}/n\mathbb{Z}\).
7.1 Fabrication des clés
Bob choisit deux nombres premiers distincts \(p\) et \(q\), puis calcule \(n=pq\) et \(\varphi(n)=(p-1)(q-1)\). Il choisit ensuite un entier \(e\) premier avec \(\varphi(n)\), et calcule \(d\) tel que \(ed\equiv 1\ [\varphi(n)]\). La clé publique est le couple \((n,e)\) ; la clé privée est \(d\).
- Chiffrement d’un message \(m\in\{0,\dots,n-1\}\) : \(c\equiv m^e\ [n]\).
- Déchiffrement : \(m\equiv c^d\ [n]\).
Pour tout entier \(m\), on a \(m^{ed}\equiv m\ [n]\). Le déchiffrement redonne donc bien le message.
Écrivons \(ed=1+k(p-1)(q-1)\) avec \(k\in\mathbb{N}\). Travaillons d’abord modulo \(p\). Si \(p\) ne divise pas \(m\), le petit théorème de Fermat donne \(m^{ed}=m\left(m^{p-1}\right)^{k(q-1)}\equiv m\ [p]\). Si \(p\) divise \(m\), les deux membres sont nuls modulo \(p\). Dans tous les cas, \(p\) divise \(m^{ed}-m\). De même, \(q\) divise \(m^{ed}-m\). Comme \(p\) et \(q\) sont premiers distincts, leur produit \(n\) divise \(m^{ed}-m\).
La figure résume les échanges : seule la clé publique circule, et la clé privée reste chez Bob.
7.2 Calculer vite une puissance modulaire
- Écrire l’exposant en base \(2\), par exemple \(5=4+1\).
- Calculer les carrés successifs \(m\), \(m^2\), \(m^4\), \(m^8\)… en réduisant modulo \(n\) à chaque étape.
- Multiplier les puissances utiles, en réduisant encore après chaque produit.
Cette méthode demande environ \(2\log_2(e)\) multiplications, au lieu de \(e-1\).
Prenons \(p=13\) et \(q=19\). Alors \(n=247\) et \(\varphi(n)=12\times 18=216\). L’exposant \(e=5\) convient, car \(216=2^3\times 3^3\). Ensuite, \(5\times 173=865=4\times 216+1\), donc \(d=173\). Chiffrons \(m=42\). On a \(42^2=1764\equiv 35\ [247]\), puis \(42^4\equiv 35^2=1225\equiv -10\ [247]\). Enfin, \(42^5\equiv -10\times 42=-420\equiv 74\ [247]\). Le message chiffré est donc \(c=74\). Un calcul analogue, plus long, donne \(74^{173}\equiv 42\ [247]\).
Remarque :
Connaître \(\varphi(n)\) revient à connaître la factorisation de \(n\). En effet, \(p+q=n-\varphi(n)+1\) et \(pq=n\) : les facteurs sont les racines d’un trinôme. C’est pourquoi \(p\) et \(q\) doivent rester secrets. En pratique, on les choisit avec plusieurs centaines de chiffres.
Les erreurs fréquentes
- Simplifier par une classe non inversible : de \(\overline{6}x=\overline{6}y\) dans \(\mathbb{Z}/9\mathbb{Z}\), on ne peut pas déduire \(x=y\).
- Appliquer le théorème d’Euler sans vérifier que \(a\) est premier avec \(n\).
- Utiliser le théorème chinois avec des modules qui ne sont pas premiers entre eux.
- Réduire l’exposant modulo \(n\) au lieu de \(\varphi(n)\) : pour \(a\wedge n=1\), on a \(a^k\equiv a^{k\bmod\varphi(n)}\ [n]\), et non \(a^{k\bmod n}\).
- Calculer la clé privée RSA comme inverse de \(e\) modulo \(n\), alors qu’il faut l’inverser modulo \(\varphi(n)\).
- Croire qu’un idéal est un sous-anneau : un idéal contenant \(1\) est l’anneau entier.
Fiche mémo
- Idéal : sous-groupe additif qui absorbe les produits. Les idéaux de \(\mathbb{Z}\) sont les \(n\mathbb{Z}\).
- \(a\equiv b\ [n]\) signifie \(n\mid a-b\) ; la congruence est compatible avec \(+\) et \(\times\).
- \(\mathbb{Z}/n\mathbb{Z}=\{\overline{0},\dots,\overline{n-1}\}\) est un anneau commutatif à \(n\) éléments.
- \(\overline{a}\) est inversible si et seulement si \(a\wedge n=1\) ; l’inverse se lit dans une relation de Bézout.
- \(\mathbb{Z}/n\mathbb{Z}\) est un corps si et seulement si \(n\) est premier.
- \(\varphi\) se calcule à partir des facteurs premiers de \(n\), et \(a^{\varphi(n)}\equiv 1\ [n]\) si \(a\wedge n=1\).
- Théorème chinois : si \(m\wedge n=1\), \(\mathbb{Z}/mn\mathbb{Z}\simeq\mathbb{Z}/m\mathbb{Z}\times\mathbb{Z}/n\mathbb{Z}\).
- Dans \(\mathbb{F}_p\), \(p\) impair : \(\frac{p-1}{2}\) carrés non nuls, et \(a\) est un carré si et seulement si \(a^{\frac{p-1}{2}}=1\).
- RSA : \(n=pq\), \(ed\equiv 1\ [\varphi(n)]\), chiffrement \(m\mapsto m^e\), déchiffrement \(c\mapsto c^d\) modulo \(n\).
Questions fréquentes
Pourquoi doit-on vérifier que les opérations de Z/nZ sont bien définies ?
Une classe possède une infinité de représentants. Si le résultat de la somme ou du produit dépendait du représentant choisi, la définition n’aurait aucun sens. La compatibilité de la congruence avec l’addition et la multiplication garantit justement que tous les représentants donnent la même classe.
Le théorème d'Euler remplace-t-il celui de Fermat ?
Le petit théorème de Fermat concerne un module premier p et donne a puissance p-1 congru à 1. Le théorème d’Euler le généralise à un module n quelconque, avec l’exposant phi(n), à condition que a soit premier avec n. Pour n premier, les deux énoncés coïncident.
Que faire si les modules d'un système de congruences ne sont pas premiers entre eux ?
Le théorème chinois ne s’applique plus directement. Vous devez d’abord vérifier la compatibilité : les seconds membres doivent être congrus modulo le pgcd des modules. Si c’est le cas, une substitution donne une solution unique modulo le ppcm ; sinon, il n’y a aucune solution.
Pourquoi RSA est-il considéré comme sûr ?
Retrouver la clé privée d revient à connaître phi(n), donc à factoriser n. Lorsque p et q comptent chacun quelques centaines de chiffres, les meilleures méthodes actuelles mettraient un temps démesuré à décomposer n. La sécurité repose donc sur cette difficulté pratique, et non sur un théorème.
Pour aller plus loin
- S’exercer : exercices corrigés de L2 de maths sur anneau Z/nZ et RSA
- Chapitre d’avant : Polynômes annulateurs et trigonalisation
- Chapitre d’après : Groupes, théorème de Lagrange et permutations
- Vérifier ses acquis : QCM de L2 de maths sur anneau Z/nZ et RSA
- Contrôle corrigé en temps limité : Calculs dans Z/nZ et RSA : contrôle de maths en L2
- Tous les chapitres : le sommaire de la L2 de maths
- Après le bac : les maths post-bac, de la MPSI à la L3
Télécharger ou imprimer cette fiche «anneau Z/nZ et RSA en L2 de maths : cours et méthodes» au format PDF afin de pouvoir travailler en totale autonomie.
