Corrigé des exercices : Anneau Z/nZ et RSA en L2 de maths

---

---

Pour démarrer

Corrigé de l’exercice 1 – Premiers calculs dans Z/14Z

Idée clé : on calcule dans \(\mathbb{Z}\), puis on réduit modulo \(14\) à chaque étape.

1. D’abord, \(9+8=17=14+3\), donc \(\overline{9}+\overline{8}=\overline{3}\). Ensuite, \(9\times 8=72=5\times 14+2\), donc \(\overline{9}\times\overline{8}=\overline{2}\). Enfin, \(\overline{5}+\overline{9}=\overline{14}=\overline{0}\). Les résultats sont \(\overline{3}\), \(\overline{2}\) et \(-\overline{5}=\overline{9}\).
2. On a \(3^5=243=17\times 14+5\), donc \(\overline{3}^5=\overline{5}\). De plus, \(3\wedge 14=1\), donc \(\overline{3}\) est inversible. Or \(3\times 5=15\equiv 1\ [14]\). Ainsi, \(\overline{3}^5=\overline{5}\) et \(\overline{3}^{-1}=\overline{5}\). On en déduit au passage \(\overline{3}^6=\overline{1}\), ce qui est conforme au théorème d’Euler, puisque \(\varphi(14)=6\).
3. On a \(4\times 7=28=2\times 14\). Donc \(\overline{4}\times\overline{7}=\overline{0}\) avec \(\overline{7}\neq\overline{0}\). Si \(\overline{4}\) était inversible, on aurait \(\overline{7}=\overline{4}^{-1}\,\overline{4}\,\overline{7}=\overline{0}\), ce qui est faux.

Corrigé de l’exercice 2 – Lecture de la table de multiplication de Z/8Z

Idée clé : une classe est inversible exactement quand sa ligne contient un \(1\).

1. Les lignes \(1\), \(3\), \(5\) et \(7\) contiennent un \(1\), sur la diagonale. En effet, \(9\), \(25\) et \(49\) sont congrus à \(1\) modulo \(8\). Les inversibles sont \(\overline{1}\), \(\overline{3}\), \(\overline{5}\), \(\overline{7}\), et chacun est son propre inverse. On retrouve les classes premières avec \(8\), et \(\varphi(8)=4\).
2. Les lignes \(2\), \(4\) et \(6\) contiennent un \(0\) hors de la colonne \(0\) : par exemple, \(\overline{2}\times\overline{4}=\overline{0}\) et \(\overline{6}\times\overline{4}=\overline{0}\). Les diviseurs de zéro sont \(\overline{2}\), \(\overline{4}\) et \(\overline{6}\).
3. Comme \(\overline{3}^{-1}=\overline{3}\), l’équation \(\overline{3}x=\overline{5}\) donne \(x=\overline{15}=\overline{7}\). Ensuite, la ligne \(2\) contient \(4\) dans les colonnes \(2\) et \(6\) : \(\overline{2}x=\overline{4}\) a deux solutions. Enfin, la ligne \(2\) ne contient que des valeurs paires. Solutions : \(\overline{7}\) ; puis \(\overline{2}\) et \(\overline{6}\) ; aucune pour \(\overline{2}x=\overline{3}\).

La figure classe les huit éléments de \(\mathbb{Z}/8\mathbb{Z}\) selon ces résultats.

Corrigé de l’exercice 3 – Somme et intersection d’idéaux de Z

Idée clé : on démontre une égalité d’ensembles par double inclusion.

1. Tout élément \(12a+18b\) vaut \(6(2a+3b)\) : il est dans \(6\mathbb{Z}\). Réciproquement, \(6=18-12\) appartient à \(12\mathbb{Z}+18\mathbb{Z}\). Or cet ensemble est un idéal, donc il contient \(6k\) pour tout \(k\). Ainsi, \(12\mathbb{Z}+18\mathbb{Z}=6\mathbb{Z}\), et \(6=12\wedge 18\).
2. Un entier est dans l’intersection s’il est multiple commun de \(12=2^2\times 3\) et de \(18=2\times 3^2\). C’est le cas si et seulement si il est multiple de \(2^2\times 3^2=36\). Donc \(m=36\), le ppcm de \(12\) et \(18\).
3. L’ensemble \(2\mathbb{N}\) contient \(2\) mais pas \(-2\) : ce n’est pas un sous-groupe. Ensuite, \(2\) et \(3\) appartiennent à \(2\mathbb{Z}\cup 3\mathbb{Z}\), mais pas leur somme \(5\). Aucun de ces deux ensembles n’est un idéal.

Corrigé de l’exercice 4 – Inverse modulaire par Euclide étendu

Idée clé : l’inverse est le coefficient de \(31\) dans une relation de Bézout entre \(31\) et \(74\).

1. Les divisions successives sont \(74=2\times 31+12\), \(31=2\times 12+7\), \(12=7+5\), \(7=5+2\) et \(5=2\times 2+1\). Le dernier reste non nul vaut \(1\). Donc \(31\wedge 74=1\) et \(\overline{31}\) est inversible.
2. On remonte : \(1=5-2\times 2=3\times 5-2\times 7=3\times 12-5\times 7=13\times 12-5\times 31=13\times 74-31\times 31\). Par conséquent, \(31\times(-31)\equiv 1\ [74]\). L’inverse est \(\overline{-31}=\overline{43}\). Vérification : \(31\times 43=1333=18\times 74+1\).
3. On multiplie par \(\overline{43}\) : \(x\equiv 5\times 43=215\equiv 67\ [74]\). Vérification : \(31\times 67=2077=28\times 74+5\). Les solutions sont les entiers \(67+74k\), \(k\in\mathbb{Z}\).

À retenir : la remontée d’Euclide est la partie la plus fragile du calcul. C’est pourquoi on garde une seule égalité, que l’on réécrit à chaque étape en remplaçant le plus petit reste. Ensuite, la vérification finale \(31\times 43\equiv 1\) ne coûte qu’une multiplication. Enfin, une fois l’inverse connu, toute équation \(31x\equiv b\ [74]\) se résout immédiatement.

Corrigé de l’exercice 5 – Grandes puissances et petit théorème de Fermat

Idée clé : modulo un premier \(p\), on réduit l’exposant modulo \(p-1\) dès que la base n’est pas multiple de \(p\).

1. Comme \(7\) est premier et ne divise pas \(3\), on a \(3^6\equiv 1\ [7]\). Or \(100=6\times 16+4\), donc \(3^{100}\equiv 3^4=81\equiv 4\ [7]\). Le reste vaut \(4\).
2. De même, \(2^{12}\equiv 1\ [13]\) et \(2026=12\times 168+10\). Ainsi, \(2^{2026}=\left(2^{12}\right)^{168}\times 2^{10}\) a le même reste que \(2^{10}=1024\). Or \(1024=78\times 13+10\). Le reste vaut \(10\).
3. Si \(13\) divise \(n\), les deux termes \(n^{13}\) et \(n\) sont multiples de \(13\). Sinon, \(n^{12}\equiv 1\ [13]\), donc \(n^{13}\equiv n\ [13]\). Dans tous les cas, \(13\) divise \(n^{13}-n\).

La figure montre la périodicité des restes de \(2^k\) modulo \(13\), de période \(12\).

Corrigé de l’exercice 6 – Calculs d’indicatrice d’Euler

Idée clé : on factorise \(n\), puis on multiplie \(n\) par les facteurs \(1-\frac{1}{p}\), un pour chaque premier \(p\) qui divise \(n\).

1. On a \(36=2^2\times 3^2\), donc \(\varphi(36)=36\times\frac{1}{2}\times\frac{2}{3}=12\). Ensuite, \(97\) est premier, donc \(\varphi(97)=96\). Puis \(\varphi(100)=100\times\frac{1}{2}\times\frac{4}{5}=40\). Enfin, \(2026=2\times 1013\), donc \(\varphi(2026)=1\times 1012\). Résultats : \(12\), \(96\), \(40\) et \(1012\).
2. Soit \(p\) premier divisant \(n\), avec \(p^k\) exactement. Alors \(\varphi(p^k)=p^{k-1}(p-1)\) divise \(4\), par multiplicativité. D’abord, \(p-1\) divise \(4\), donc \(p\in\{2,3,5\}\). Ensuite, \(3^2\) et \(5^2\) ne peuvent pas diviser \(n\), car \(3\) et \(5\) ne divisent pas \(4\). Enfin, \(2^k\) avec \(k\leq 3\). On écrit \(n=2^a3^b5^c\), avec \(b,c\in\{0,1\}\). Si \(c=1\), il faut \(\varphi(2^a)\times\varphi(3^b)=1\), d’où \(n=5\) ou \(n=10\). Si \(c=0\) et \(b=1\), il faut \(\varphi(2^a)=2\), d’où \(n=12\). Si \(b=c=0\), il faut \(\varphi(2^a)=4\), d’où \(n=8\). Les solutions sont \(5\), \(8\), \(10\) et \(12\).

Corrigé de l’exercice 7 – Dernier chiffre d’une puissance

Idée clé : le dernier chiffre est le reste modulo \(10\) ; le théorème d’Euler demande une base première avec \(10\).

1. On a \(\varphi(10)=4\) et \(7\wedge 10=1\), donc \(7^4\equiv 1\ [10]\). Comme \(2026=4\times 506+2\), on obtient \(7^{2026}\equiv 7^2=49\equiv 9\ [10]\). Le dernier chiffre est \(9\).
2. Ici, \(4\wedge 10=2\) : le théorème d’Euler ne s’applique pas. On calcule directement : \(4^1=4\), \(4^2=16\equiv 6\), puis \(4^3\equiv 6\times 4=24\equiv 4\ [10]\). Par récurrence, \(4^k\equiv 4\) si \(k\) est impair et \(4^k\equiv 6\) si \(k\geq 2\) est pair. Le dernier chiffre de \(4^{2026}\) est \(6\).

Pour s’entraîner

Corrigé de l’exercice 8 – Un système de trois congruences

Idée clé : les modules \(5\), \(7\) et \(9\) sont premiers entre eux deux à deux ; on résout les congruences une par une.

1. Le nombre \(x\) vérifie \(x\equiv 2\ [5]\), \(x\equiv 3\ [7]\) et \(x\equiv 4\ [9]\). Les modules sont premiers entre eux deux à deux et \(5\times 7\times 9=315\). Par le théorème chinois, appliqué deux fois, il existe une unique solution modulo \(315\).
2. On écrit \(x=2+5k\). La deuxième congruence donne \(5k\equiv 1\ [7]\). Or \(5\times 3=15\equiv 1\ [7]\), donc \(k\equiv 3\ [7]\) et \(x\equiv 17\ [35]\). Ensuite, on écrit \(x=17+35j\). La troisième congruence donne \(17+35j\equiv 4\ [9]\), soit \(8+8j\equiv 4\ [9]\), donc \(8j\equiv 5\ [9]\). Comme \(8\equiv -1\ [9]\), on obtient \(j\equiv -5\equiv 4\ [9]\). Ainsi, \(x\equiv 17+140=157\ [315]\). La solution est \(x\equiv 157\ [315]\).
3. Vérification : \(157=31\times 5+2=22\times 7+3=17\times 9+4\). Il y a donc \(157\) pièces.

À retenir : la méthode par substitution évite de chercher trois relations de Bézout. En effet, à chaque étape, on n’inverse qu’un petit nombre modulo un petit module : ici \(5\) modulo \(7\), puis \(8\) modulo \(9\). De plus, le résultat intermédiaire \(x\equiv 17\ [35]\) se vérifie aussitôt. Cette démarche s’étend sans difficulté à un nombre quelconque de congruences.

Corrigé de l’exercice 9 – Congruences à modules non premiers entre eux

Idée clé : on reporte la première congruence dans la seconde, puis on divise par le pgcd quand c’est possible.

1. Avec \(x=3+8k\), la seconde congruence devient \(8k\equiv 4\ [12]\), soit \(12\mid 8k-4\). En divisant par \(4\), on obtient \(2k\equiv 1\ [3]\), donc \(k\equiv 2\ [3]\). Ainsi, \(k=2+3j\) et \(x=19+24j\). Vérification : \(19=2\times 8+3=12+7\). Les solutions sont les \(x\equiv 19\ [24]\), où \(24\) est le ppcm de \(8\) et \(12\).
2. La première congruence impose \(x\) impair, car \(6\) est pair. La seconde impose \(x\) pair, pour la même raison. Le système n’a donc aucune solution.
3. Si \(x\) est solution, alors \(d=m\wedge n\) divise \(x-a\) et \(x-b\), donc divise \(a-b\). Une condition nécessaire est \(a\equiv b\ [m\wedge n]\). Dans la question 1, \(7-3=4\) est multiple de \(4\) ; dans la question 2, \(4-1=3\) n’est pas pair.

Corrigé de l’exercice 10 – Équation linéaire dans Z/30Z

Idée clé : \(\overline{12}\) n’est pas inversible modulo \(30\) ; on divise donc tout par \(12\wedge 30=6\).

1. L’équation signifie \(30\mid 12x-18\), c’est-à-dire \(30k=12x-18\) pour un entier \(k\). En divisant par \(6\), on obtient \(5k=2x-3\). Ainsi, l’équation équivaut à \(2x\equiv 3\ [5]\).
2. Dans \(\mathbb{F}_5\), l’inverse de \(\overline{2}\) est \(\overline{3}\). Donc \(x\equiv 9\equiv 4\ [5]\). Les solutions dans \(\{0,\dots,29\}\) sont \(4\), \(9\), \(14\), \(19\), \(24\) et \(29\) : il y en a six. Par exemple, \(12\times 4=48=30+18\).
3. Si \(12x\equiv 20\ [30]\), alors \(6\), qui divise \(30\) et \(12x\), diviserait \(20\). C’est faux : cette équation n’a aucune solution.

Corrigé de l’exercice 11 – Inversibles et diviseurs de zéro

Idée clé : le pgcd \(d\) fournit explicitement un partenaire qui annule \(\overline{a}\).

1. Écrivons \(a=da^{\prime}\) et \(n=dn^{\prime}\). Alors \(a\times n^{\prime}=a^{\prime}dn^{\prime}=a^{\prime}n\), qui est multiple de \(n\). De plus, \(1\leq n^{\prime}<n\) car \(d>1\), donc \(\overline{n^{\prime}}\neq\overline{0}\). Ainsi, \(\overline{a}\) est un diviseur de zéro.
2. Si \(\overline{a}\) est inversible et \(\overline{a}\,\overline{b}=\overline{0}\), on multiplie par \(\overline{a}^{-1}\) : \(\overline{b}=\overline{0}\). Un inversible n’est donc jamais diviseur de zéro.
3. Soit \(\overline{a}\neq\overline{0}\). Si \(a\wedge n=1\), la classe est inversible. Sinon, la question 1 montre qu’elle est diviseur de zéro. La question 2 interdit les deux à la fois. Les deux familles sont donc disjointes et recouvrent toutes les classes non nulles.

Corrigé de l’exercice 12 – Équations du second degré modulo n

Idée clé : dans un corps de caractéristique différente de \(2\), la mise sous forme canonique fonctionne comme dans \(\mathbb{R}\).

1. On a \(2\times 7=14\equiv 1\ [13]\), donc \(\overline{2}^{-1}=\overline{7}\). Ensuite, \(4^2=16=13+3\). Ainsi, \(\overline{2}^{-1}=\overline{7}\) et \(\overline{4}^2=\overline{3}\).
2. La moitié de \(3\) est \(3\times 7=21\equiv 8\). Or \((x+8)^2=x^2+16x+64=x^2+3x+12\) dans \(\mathbb{F}_{13}\). L’équation s’écrit donc \((x+8)^2=12-9=3=4^2\). Comme \(\mathbb{F}_{13}\) est intègre, \((x+8-4)(x+8+4)=0\) donne \(x=-4=9\) ou \(x=-12=1\). Les solutions sont \(\overline{1}\) et \(\overline{9}\). Vérification : \(1+3+9=13\) et \(81+27+9=117=9\times 13\).
3. Les carrés de \(1\), \(3\), \(5\), \(7\) valent \(1\), \(9\), \(25\), \(49\), tous congrus à \(1\) modulo \(8\). Les carrés des classes paires sont pairs. Les solutions sont \(\overline{1}\), \(\overline{3}\), \(\overline{5}\) et \(\overline{7}\). Il n’y a pas de contradiction : \(\mathbb{Z}/8\mathbb{Z}\) n’est pas un corps, ni même un anneau intègre. Par exemple, \((x-1)(x+1)=\overline{0}\) pour \(x=\overline{3}\), alors qu’aucun facteur n’est nul.

Corrigé de l’exercice 13 – Carrés modulo 11 et critère d’Euler

Idée clé : il suffit d’élever au carré \(1,\dots,5\), car \(x\) et \(-x\) ont le même carré.

1. On trouve \(1^2=1\), \(2^2=4\), \(3^2=9\), \(4^2=16\equiv 5\) et \(5^2=25\equiv 3\). Les carrés non nuls sont \(1\), \(3\), \(4\), \(5\) et \(9\), soit \(\frac{11-1}{2}=5\) classes, comme prévu.
2. On a \(5^2\equiv 3\), \(5^4\equiv 9\), donc \(5^5\equiv 45\equiv 1\ [11]\). Ensuite, \(7^2=49\equiv 5\), \(7^4\equiv 25\equiv 3\), donc \(7^5\equiv 21\equiv -1\ [11]\). Par le critère d’Euler, \(5\) est un carré (en effet \(4^2\equiv 5\)), et \(7\) n’en est pas un.
3. La classe \(-1=10\) n’est pas dans la liste. Donc \(-1\) n’est pas un carré dans \(\mathbb{F}_{11}\), ce qui est cohérent avec \(11\equiv 3\ [4]\).

Corrigé de l’exercice 14 – Les idéaux de Z/12Z

Idée clé : on remonte l’idéal dans \(\mathbb{Z}\), où tous les idéaux sont connus.

1. Si \(x\) et \(y\) sont dans \(J\), alors \(\overline{x-y}=\overline{x}-\overline{y}\in I\), donc \(x-y\in J\). De plus, \(0\in J\). Pour \(a\in\mathbb{Z}\), \(\overline{ax}=\overline{a}\,\overline{x}\in I\) par absorption. Donc \(J\) est un idéal de \(\mathbb{Z}\). Enfin, tout multiple de \(12\) a pour classe \(\overline{0}\in I\), d’où \(12\mathbb{Z}\subset J\).
2. Par le cours, \(J=d\mathbb{Z}\) avec \(d\geq 0\). Comme \(12\in J\), \(d\) divise \(12\). Ensuite, \(I\) est l’ensemble des classes des éléments de \(J\), c’est-à-dire des \(\overline{dk}=\overline{k}\,\overline{d}\). Ainsi, \(I\) est l’idéal engendré par \(\overline{d}\), avec \(d\mid 12\).
3. Les diviseurs de \(12\) sont \(1\), \(2\), \(3\), \(4\), \(6\) et \(12\). L’idéal engendré par \(\overline{d}\) contient les classes \(\overline{0},\overline{d},\dots\), soit \(\frac{12}{d}\) éléments. On obtient six idéaux, de cardinaux \(12\), \(6\), \(4\), \(3\), \(2\) et \(1\). Ils sont distincts, car \(I\) détermine \(J\), donc \(d\).

Corrigé de l’exercice 15 – Le théorème chinois pour Z/15Z

Idée clé : \(e_1\) et \(e_2\) correspondent aux couples \((1,0)\) et \((0,1)\) de \(\mathbb{Z}/3\mathbb{Z}\times\mathbb{Z}/5\mathbb{Z}\).

1. Les multiples de \(5\) entre \(0\) et \(14\) sont \(0\), \(5\), \(10\), et seul \(10\) vaut \(1\) modulo \(3\). De même, parmi \(0\), \(3\), \(6\), \(9\), \(12\), seul \(6\) vaut \(1\) modulo \(5\). Donc \(e_1=10\) et \(e_2=6\).
2. On calcule \(100=6\times 15+10\), \(36=2\times 15+6\) et \(60=4\times 15\). Ainsi, \(\overline{10}^2=\overline{10}\), \(\overline{6}^2=\overline{6}\) et \(\overline{10}\times\overline{6}=\overline{0}\).
3. La classe \(2e_1+4e_2\) correspond au couple \(2(1,0)+4(0,1)=(2,4)\). Or \(2\times 10+4\times 6=44\equiv 14\ [15]\). Vérification : \(14=4\times 3+2=2\times 5+4\). La solution est \(x\equiv 14\ [15]\).
4. Par l’isomorphisme chinois, \(\overline{x}^2=\overline{x}\) équivaut à la même équation dans \(\mathbb{F}_3\) et dans \(\mathbb{F}_5\). Dans un corps, \(y(y-1)=0\) donne \(y=0\) ou \(y=1\). Il y a donc quatre couples : \((0,0)\), \((1,1)\), \((1,0)\) et \((0,1)\). Les solutions sont \(\overline{0}\), \(\overline{1}\), \(\overline{10}\) et \(\overline{6}\).

La figure situe ces classes dans la grille des restes modulo \(3\) et modulo \(5\).

Corrigé de l’exercice 16 – RSA avec de petits nombres

Idée clé : la clé privée est l’inverse de \(e\) modulo \(\varphi(n)\), et non modulo \(n\).

1. On a \(n=55\) et \(\varphi(n)=4\times 10=40=2^3\times 5\). Comme \(3\) ne divise pas \(40\), l’exposant \(e=3\) est admissible.
2. On cherche \(d\) tel que \(3d\equiv 1\ [40]\). Or \(3\times 27=81=2\times 40+1\). Donc \(d=27\).
3. On a \(8^3=512=9\times 55+17\). Le message chiffré est \(c=17\).
4. On calcule les carrés successifs modulo \(55\) : \(17^2=289\equiv 14\), \(17^4\equiv 196\equiv 31\), \(17^8\equiv 961\equiv 26\) et \(17^{16}\equiv 676\equiv 16\). Comme \(27=16+8+2+1\), on obtient \(16\times 26=416\equiv 31\), puis \(31\times 14=434\equiv 49\), enfin \(49\times 17=833\equiv 8\). On retrouve bien \(m=8\).

À retenir : avec des nombres aussi petits, le système n’offre évidemment aucune sécurité. Par exemple, un espion factorise \(55\) de tête. Cependant, toutes les étapes sont exactement celles d’un vrai chiffrement : choix de \(e\), inversion modulo \(\varphi(n)\), exponentiation rapide. Seule la taille des nombres change, et avec elle la difficulté de factoriser \(n\).

Pour approfondir

Corrigé de l’exercice 17 – Le théorème de Wilson

Idée clé : dans le produit de toutes les classes non nulles, chaque classe se simplifie avec son inverse, sauf celles qui sont leur propre inverse.

1. La figure associe \(2\) et \(7\), \(3\) et \(9\), \(4\) et \(10\), \(5\) et \(8\), \(6\) et \(11\). Chacun de ces couples a pour produit \(1\) modulo \(13\). Restent \(1\) et \(12\). Donc \(12!\equiv 1\times 12\equiv -1\ [13]\).
2. Une classe est son propre inverse si et seulement si \(x^2=1\), soit \((x-1)(x+1)=0\). Comme \(\mathbb{F}_p\) est intègre, on obtient \(x=\overline{1}\) ou \(x=\overline{-1}\), ces deux classes étant égales lorsque \(p=2\).
3. Pour \(p=2\), on a \(1!=1\equiv -1\ [2]\). Pour \(p\) impair, les classes autres que \(\pm\overline{1}\) se regroupent par paires \(\{x,x^{-1}\}\) de produit \(\overline{1}\). Il reste \(\overline{1}\times\overline{-1}\). Ainsi, \((p-1)!\equiv -1\ [p]\).
4. Par Wilson, \(16!\equiv -1\equiv 16\ [17]\). Ensuite, \(16!=16\times 15!\) et \(16\equiv -1\), donc \(-15!\equiv -1\). On obtient \(16!\equiv 16\) et \(15!\equiv 1\) modulo \(17\).
5. Soit \(n=ab\) avec \(1<a<n\). Alors \(a\leq n-1\), donc \(a\) divise \((n-1)!\). Si l’on avait \((n-1)!\equiv -1\ [n]\), \(a\) diviserait aussi \((n-1)!+1\), donc diviserait \(1\). C’est absurde : la congruence de Wilson caractérise les nombres premiers.

À retenir : le théorème de Wilson fournit donc un test de primalité exact. En pratique, il est pourtant inutilisable, car calculer \((n-1)!\) modulo \(n\) demande environ \(n\) multiplications. Par conséquent, on lui préfère des tests fondés sur le petit théorème de Fermat ou sur le critère d’Euler, beaucoup plus rapides grâce à l’exponentiation rapide.

Corrigé de l’exercice 18 – Quand -1 est-il un carré modulo p ?

Idée clé : le critère d’Euler ramène la question à la parité de \(\frac{p-1}{2}\).

1. Appliquons le critère d’Euler à \(a=-1\) : la condition à tester est \((-1)^{\frac{p-1}{2}}=1\). Puisque \(p\) est impair, \(1\neq -1\) dans \(\mathbb{F}_p\). Cette égalité équivaut donc à \(\frac{p-1}{2}\) pair. Ainsi, \(-1\) est un carré si et seulement si \(p\equiv 1\ [4]\).
2. On a \(5^2=25=26-1\) et \(4^2=16=17-1\). On peut prendre \(x=5\) et \(y=4\).
3. On regroupe les facteurs de \((p-1)!\) en \(k\) et \(p-k\), pour \(1\leq k\leq\frac{p-1}{2}\). Comme \(p-k\equiv -k\ [p]\), on obtient \((p-1)!\equiv(-1)^{\frac{p-1}{2}}\left(\left(\frac{p-1}{2}\right)!\right)^2\ [p]\). Or \(\frac{p-1}{2}\) est pair, et Wilson donne \((p-1)!\equiv -1\). Donc \(x^2\equiv -1\ [p]\). Pour \(p=13\), on trouve \(6!=720=55\times 13+5\), et l’on retrouve \(x=5\).
4. Posons \(M=4(N!)^2+1\), qui est impair et supérieur à \(1\). Soit \(p\) un facteur premier de \(M\). Si \(p\leq N\), alors \(p\) divise \(N!\), donc \(p\) divise \(M-4(N!)^2=1\) : c’est absurde. Ainsi, \(p>N\), et \(p\) est impair. Ensuite, \(x=2\,N!\) vérifie \(x^2\equiv -1\ [p]\). D’après la question 1, \(p\equiv 1\ [4]\). Pour tout \(N\), il existe donc un premier \(p>N\) congru à \(1\) modulo \(4\) : il y en a une infinité.

Corrigé de l’exercice 19 – Problème – Un chiffrement RSA complet et son attaque

Idée clé : on fabrique les clés avec Bézout, on chiffre par exponentiation rapide, puis on déchiffre plus vite grâce au théorème chinois.

1. On a \(n=29\times 41=1189\) et \(\varphi(n)=28\times 40=1120=2^5\times 5\times 7\). Comme \(3\) ne divise pas \(1120\), \(e=3\) est premier avec \(\varphi(n)\).
2. On a \(1120=3\times 373+1\), donc \(3\times(-373)\equiv 1\ [1120]\). La clé privée est \(d=1120-373=747\). Vérification : \(3\times 747=2241=2\times 1120+1\).
3. On a \(100^2=10000=8\times 1189+488\), puis \(488\times 100=48800=41\times 1189+51\). Le message chiffré est \(c=51\).
4. D’abord, \(747=26\times 28+19=18\times 40+27\), donc \(d\equiv 19\ [28]\) et \(d\equiv 27\ [40]\). Ensuite, \(c\equiv 22\equiv -7\ [29]\) et \(c\equiv 10\ [41]\).
   • Modulo \(29\) : \((-7)^2\equiv 20\), \((-7)^4\equiv 400\equiv 23\), \((-7)^8\equiv 529\equiv 7\) et \((-7)^{16}\equiv 49\equiv 20\). Comme \(19=16+2+1\), on obtient \(20\times 20\times(-7)\equiv 23\times(-7)=-161\equiv 13\ [29]\).
   • Modulo \(41\) : \(10^2\equiv 18\), \(10^4\equiv 324\equiv 37\), puis \(10^5\equiv 370=9\times 41+1\equiv 1\). Comme \(27=5\times 5+2\), on obtient \(10^{27}\equiv 10^2\equiv 18\ [41]\).

   Il reste à résoudre \(m\equiv 13\ [29]\) et \(m\equiv 18\ [41]\). On a \(29\times 17=493=12\times 41+1\) et \(41\times 17=697=24\times 29+1\). Donc \(e_1=697\) et \(e_2=493\) conviennent. Ainsi, \(m\equiv 13\times 697+18\times 493=9061+8874=17935\ [1189]\). Or \(17935=15\times 1189+100\). On retrouve \(m=100\).

5. Si \(29\) ne divise pas \(c\), le petit théorème de Fermat donne \(c^{28}\equiv 1\ [29]\). En écrivant \(d=28q+r\), on a \(c^d=(c^{28})^qc^r\equiv c^r\ [29]\). Si \(29\) divise \(c\), les deux puissances sont nulles modulo \(29\), car \(r\geq 1\) ici. On peut donc remplacer \(d\) par \(d\bmod 28\).
6. On a \(\varphi(n)=(p-1)(q-1)=n-(p+q)+1\). Donc \(p+q=n-\varphi(n)+1=70\) et \(pq=1189\). Ainsi, \(p\) et \(q\) sont les racines de \(X^2-70X+1189\). Le discriminant vaut \(4900-4756=144=12^2\). On retrouve \(p=\frac{70-12}{2}=29\) et \(q=\frac{70+12}{2}=41\). Connaître \(\varphi(n)\) casse donc complètement le système.

Pour aller plus loin

Télécharger puis imprimer cette fiche en PDF.

Télécharger ou imprimer cette fiche «corrigé des exercices : Anneau Z/nZ et RSA en L2 de maths» au format PDF afin de pouvoir travailler en totale autonomie.

---

OK

 Maths PDF c'est 16 224 783 cours et exercices de maths téléchargés en PDF et 4 250 exercices.