Calculs dans Z/nZ et RSA : corrigé du contrôle de maths en L2

Télécharger en PDF Le livre des 25 contrôles corrigés en L2 PDF à imprimer Voir le livre ›

Barème du contrôle corrigé : calculs dans Z/nZ et RSA

Le corrigé détaillé : calculs dans Z/nZ et RSA

Exercice 1 – Question de cours : les idéaux de Z (3 points)

1. D’abord, \(0 = n \times 0\) appartient à \(n\mathbb{Z}\). Si \(nk\) et \(nk^{\prime}\) sont dans \(n\mathbb{Z}\), alors \(nk – nk^{\prime} = n(k – k^{\prime}) \in n\mathbb{Z}\) : c’est donc un sous-groupe. Enfin, pour \(j \in \mathbb{Z}\), on a \(j(nk) = n(jk) \in n\mathbb{Z}\). Ainsi \(n\mathbb{Z}\) est un idéal de \(\mathbb{Z}\).

2. Existence du plus petit élément

   Comme \(I \neq \{0\}\), il contient un entier \(a \neq 0\), ainsi que \(-a\), car \(I\) est un sous-groupe. Parmi \(a\) et \(-a\), l’un est strictement positif ; ainsi \(I \cap \mathbb{N}^*\) n’est pas vide. Par le principe du bon ordre sur les entiers naturels, cet ensemble possède un minimum, que l’on note \(n\).

   Double inclusion par division euclidienne

   Puisque \(n \in I\) et que \(I\) est absorbant, tout multiple \(kn\) appartient à \(I\) : on a donc \(n\mathbb{Z} \subset I\). Réciproquement, soit \(a \in I\). On écrit \(a = nq + r\) avec \(0 \leq r < n\). Le reste \(r = a – qn\) est encore dans \(I\) : c’est en effet la différence de deux éléments de \(I\). Si \(r\) était strictement positif, il contredirait la minimalité de \(n\) ; par conséquent \(r = 0\) et \(a \in n\mathbb{Z}\). On conclut que \(I = n\mathbb{Z}\).

3. Les divisions successives donnent \(84 = 2 \times 30 + 24\), puis \(30 = 1 \times 24 + 6\), enfin \(24 = 4 \times 6\). En remontant, \(6 = 30 – 24 = 30 – (84 – 2 \times 30) = 3 \times 30 – 84\). On peut donc prendre \(u = -1\) et \(v = 3\). Ainsi \(6 \in J\), d’où \(6\mathbb{Z} \subset J\). Inversement, \(84 = 6 \times 14\) et \(30 = 6 \times 5\) sont dans l’idéal \(6\mathbb{Z}\), qui est stable par somme, donc \(J \subset 6\mathbb{Z}\). Finalement \(J = 6\mathbb{Z}\).

Barème : 1) trois propriétés vérifiées (0,5) ; 2) existence de \(n\) (0,5), inclusion \(n\mathbb{Z} \subset I\) (0,25), division euclidienne et minimalité (0,75) ; 3) relation de Bézout (0,5), double inclusion (0,5).

Piège classique : oublier de justifier que \(I\) contient un élément strictement positif. Sans le passage par \(-a\), l’ensemble \(I \cap \mathbb{N}^*\) pourrait sembler vide.

Exercice 2 – Le groupe des inversibles de Z/21Z (4 points)

1. Supposons \(\overline{a}\) inversible : il existe \(b\) tel que \(ab \equiv 1 \ [21]\), donc un entier \(k\) avec \(ab – 21k = 1\). Le théorème de Bézout donne alors \(\mathrm{pgcd}(a, 21) = 1\). Réciproquement, si \(\mathrm{pgcd}(a, 21) = 1\), Bézout fournit \(u, v\) tels que \(au + 21v = 1\). En passant aux classes, \(\overline{au} = \overline{1}\), donc \(\overline{u}\) est un inverse. Ainsi \(\overline{a}\) est inversible si et seulement si \(a\) est premier avec 21.
2. Comme \(21 = 3 \times 7\) avec 3 et 7 premiers, \(\varphi(21) = (3 – 1)(7 – 1) = 12\). En effet, parmi les classes de 0 à 20, les multiples de 3 sont au nombre de 7 et seuls 7 et 14 sont des multiples de 7 non multiples de 3. Il reste \(21 – 9 = 12\) classes. La figure compte bien 12 points bleus.
3. On divise : \(21 = 2 \times 10 + 1\), donc \(1 = 21 – 2 \times 10\). En passant modulo 21, \(\overline{10} \times \overline{-2} = \overline{1}\). L’inverse de \(\overline{10}\) est \(\overline{19}\) ; on vérifie que \(10 \times 19 = 190 = 9 \times 21 + 1\).

4. Un raisonnement modulo 3 et modulo 7

   Résoudre cette équation revient à demander que \(21\) divise \((x – 1)(x + 1)\) ; autrement dit, puisque 3 et 7 sont premiers entre eux, à \(3 \mid (x – 1)(x + 1)\) et \(7 \mid (x – 1)(x + 1)\). Comme 3 et 7 sont premiers, le lemme d’Euclide donne \(x \equiv \pm 1 \ [3]\) et \(x \equiv \pm 1 \ [7]\).

   Les quatre combinaisons

   Le théorème chinois associe à chaque couple de signes une unique classe modulo 21. Le couple \((1, 1)\) donne \(\overline{1}\), et le couple \((-1, -1)\) donne \(\overline{20}\). Pour \(x \equiv 1 \ [3]\) et \(x \equiv 6 \ [7]\), on teste 6, 13, 20 : seul 13 convient. Pour \(x \equiv 2 \ [3]\) et \(x \equiv 1 \ [7]\), on teste 1, 8, 15 : seul 8 convient. Les solutions sont \(\overline{1}\), \(\overline{8}\), \(\overline{13}\) et \(\overline{20}\) ; elles sont repérées en vert sur le cercle.

   

   Prenons par exemple la racine \(\overline{8}\) : il vient \((\overline{8} – \overline{1})(\overline{8} + \overline{1}) = \overline{7} \times \overline{9} = \overline{63} = \overline{0}\). Les classes non nulles \(\overline{7}\) et \(\overline{9}\) sont des diviseurs de zéro, donc l’anneau n’est pas intègre. D’ailleurs, un polynôme de degré 2 ne pourrait pas avoir quatre racines dans un anneau intègre.

Barème : 1) sens direct (0,5), réciproque (0,5) ; 2) calcul de \(\varphi(21)\) (0,5) ; 3) division et inverse vérifié (1) ; 4) réduction modulo 3 et 7 (0,5), quatre solutions (0,5), diviseurs de zéro (0,5).

Piège classique : conclure trop vite que \(x^2 = \overline{1}\) n’a que deux solutions. Ce réflexe vaut dans un corps, mais \(\mathbb{Z}/21\mathbb{Z}\) n’en est pas un.

Exercice 3 – Théorème d’Euler et grandes puissances (4 points)

1. Une bijection de U_n

   Le produit de deux classes inversibles est inversible, donc \(f : \overline{x} \mapsto \overline{a}\,\overline{x}\) envoie bien \(U_n\) dans \(U_n\). Si \(\overline{a}\,\overline{x} = \overline{a}\,\overline{y}\), on multiplie par l’inverse de \(\overline{a}\) et l’on obtient \(x \equiv y \ [n]\) : \(f\) est injective. Comme \(U_n\) est fini, \(f\) est une bijection de \(U_n\) sur lui-même.

   Le produit calculé deux fois

   Notons \(P\) le produit de tous les éléments de \(U_n\). Puisque \(f\) permute ces éléments et que l’anneau est commutatif, \(P\) est aussi le produit des \(\overline{a}\,\overline{x}\), soit \(P = \overline{a}^{\,\varphi(n)}\,P\). Or \(P\) est inversible, en tant que produit d’inversibles. En simplifiant par \(P\), il reste \(\overline{a^{\varphi(n)}} = \overline{1}\), soit \(a^{\varphi(n)} \equiv 1 \ [n]\).

2. Comme \(40 = 2^3 \times 5\), on a \(\varphi(40) = \varphi(8)\,\varphi(5) = 4 \times 4 = 16\). Ensuite, \(7 \times 7 = 49 \equiv 9\), puis \(9 \times 7 = 63 \equiv 23\), enfin \(23 \times 7 = 161 = 4 \times 40 + 1 \equiv 1\). Le plus petit exposant vaut donc \(k = 4\), qui divise \(\varphi(40) = 16\) sans lui être égal.
3. On a \(2026 = 4 \times 506 + 2\), donc \(7^{2026} = \left(7^4\right)^{506} \times 7^2 \equiv 1 \times 49 \equiv 9 \ [40]\). Le reste cherché est 9.
4. Ici \(\mathrm{pgcd}(13, 50) = 1\) et \(\varphi(50) = \varphi(2)\,\varphi(25) = 1 \times 20 = 20\). Comme \(403 = 20 \times 20 + 3\), le théorème d’Euler donne \(13^{403} \equiv 13^3 \ [50]\). Puis \(13^2 = 169 \equiv 19\) et \(19 \times 13 = 247 \equiv 47 \ [50]\). Le reste est 47.

Barème : 1) bijection (0,75), égalité des produits et simplification (0,75) ; 2) \(\varphi(40)\) (0,25), quatre flèches (0,5), comparaison (0,25) ; 3) réduction de l’exposant (0,75) ; 4) hypothèse et \(\varphi(50)\) (0,25), calcul (0,5).

Piège classique : simplifier par \(P\) sans dire qu’il est inversible. Dans \(\mathbb{Z}/n\mathbb{Z}\), on ne simplifie que par une classe inversible.

Exercice 4 – Congruences simultanées (4 points)

1. Comme \(6 = 2 \times 3\), la condition \(x \equiv 3 \ [6]\) équivaut à \(x \equiv 1 \ [2]\) et \(x \equiv 0 \ [3]\). Or \(x \equiv 5 \ [8]\) entraîne déjà que \(x\) est impair. Le système équivaut donc à \(x \equiv 0 \ [3]\) et \(x \equiv 5 \ [8]\), avec des modules premiers entre eux. Parmi 5, 13, 21, seul 21 est multiple de 3. Les solutions sont les entiers \(x \equiv 21 \ [24]\).
2. Si \(x \equiv 1 \ [6]\), alors \(x\) est impair ; en revanche, \(x \equiv 2 \ [4]\) impose que \(x\) soit pair. Aucun entier ne peut remplir ces deux exigences de parité opposées : l’ensemble des solutions est vide.
3. On cherche \(x = 3 + 7k\) avec \(3 + 7k \equiv 2 \ [5]\), soit \(2k \equiv 4 \ [5]\). Puisque 2 est inversible modulo 5, on obtient \(k \equiv 2 \ [5]\), d’où \(x \equiv 3 + 14 = 17 \ [35]\). Réciproquement, \(17 = 3 \times 5 + 2 = 2 \times 7 + 3\) convient. Les deux conditions équivalent bien à \(x \equiv 17 \ [35]\), l’unicité modulo 35 venant du théorème chinois.

4. L’inverse de 8 modulo 9

   Comme \(8 \times 8 = 64 = 7 \times 9 + 1\), l’inverse de 8 modulo 9 est 8 lui-même.

   Recollement modulo 315

   On pose \(x = 17 + 35k\). Or \(17 \equiv 8\) et \(35 \equiv 8\) modulo 9, donc la condition \(x \equiv 4 \ [9]\) s’écrit \(8 + 8k \equiv 4\), soit \(8k \equiv 5 \ [9]\). En multipliant par 8, \(k \equiv 40 \equiv 4 \ [9]\). Ainsi \(x = 17 + 35 \times 4 = 157\). Le système complet équivaut à \(x \equiv 157 \ [315]\).

5. Les solutions positives sont 157, 472, 787… Seule 472 est comprise entre 400 et 600. De plus, \(472 = 94 \times 5 + 2 = 67 \times 7 + 3 = 52 \times 9 + 4\). La boîte contient 472 jetons.

Barème : 1) décomposition modulo 2 et 3 (0,5), solution (0,5) ; 2) argument de parité (0,5) ; 3) résolution (0,75), réciproque (0,25) ; 4) inverse (0,25), résolution modulo 315 (0,75) ; 5) choix et vérification (0,5).

Piège classique : appliquer le théorème chinois avec les modules 6 et 8. Ils ne sont pas premiers entre eux, donc la solution n’est pas unique modulo 48 mais modulo 24.

Exercice 5 – Problème : une clé RSA de module 247 (5 points)

1. On a \(n = 13 \times 19 = 247\) et, puisque \(p\) et \(q\) sont premiers distincts, \(\varphi(n) = 12 \times 18 = 216 = 2^3 \times 3^3\). Le nombre premier 5 ne divise pas 216. Ainsi \(\varphi(n) = 216\) et \(e = 5\) est premier avec \(\varphi(n)\).
2. La division \(216 = 43 \times 5 + 1\) donne \(1 = 216 – 43 \times 5\), donc \(5 \times (-43) \equiv 1 \ [216]\). On ajoute 216 pour revenir entre 1 et 216 : \(-43 + 216 = 173\). L’exposant secret vaut \(d = 173\) ; on vérifie que \(5 \times 173 = 865 = 4 \times 216 + 1\).
3. D’abord \(10^3 = 1000 = 4 \times 247 + 12\), donc \(10^3 \equiv 12 \ [247]\). Ensuite, \(10^5 = 10^3 \times 10^2 \equiv 12 \times 100 = 1200 \ [247]\). Or \(1200 = 4 \times 247 + 212\). Le message chiffré est bien \(c = 212\).

4. Le calcul modulo 13

   On a \(212 = 16 \times 13 + 4\), donc \(c \equiv 4 \ [13]\). Comme 13 est premier et ne divise pas 4, le petit théorème de Fermat donne \(4^{12} \equiv 1 \ [13]\). Puis \(173 = 14 \times 12 + 5\), d’où \(c^{173} \equiv 4^5 \ [13]\). Enfin, \(4^2 = 16 \equiv 3\), \(4^4 \equiv 9\) et \(4^5 \equiv 36 \equiv 10 \ [13]\).

   Le calcul modulo 19

   De même, \(212 = 11 \times 19 + 3\), donc \(c \equiv 3 \ [19]\), et \(3^{18} \equiv 1 \ [19]\). Comme \(173 = 9 \times 18 + 11\), il reste à calculer \(3^{11}\). On trouve \(3^3 = 27 \equiv 8\), puis \(3^6 \equiv 64 \equiv 7\), ensuite \(3^9 \equiv 56 \equiv -1\). Ainsi \(3^{11} \equiv -9 \equiv 10 \ [19]\).

   Conclusion par le théorème chinois

   L’entier \(c^{d}\) est donc congru à 10 modulo 13 et modulo 19. Le théorème chinois, valable car 13 et 19 sont deux premiers distincts, ne laisse qu’une seule classe modulo 247 ; or 10 convient. Gaspard retrouve le message \(m = 10\).

5. Par construction, \(ed = 1 + k\,\varphi(n)\) avec \(k \in \mathbb{N}\) ; ici \(k = 4\). Si \(m\) est premier avec \(n\), le théorème d’Euler donne \(m^{\varphi(n)} \equiv 1 \ [n]\), donc \(m^{ed} = m \times \left(m^{\varphi(n)}\right)^k \equiv m \ [n]\). Le déchiffrement redonne donc toujours le message. Cependant, calculer \(d\) exige \(\varphi(n) = (p – 1)(q – 1)\), donc la factorisation de \(n\). Pour un module de plusieurs centaines de chiffres, aucune méthode connue ne la fournit en temps raisonnable : c’est pourquoi la clé publique ne trahit pas \(d\).

Barème : 1) \(n\) et \(\varphi(n)\) (0,5), primalité de \(e\) avec \(\varphi(n)\) (0,25) ; 2) relation de Bézout (0,5), valeur de \(d\) vérifiée (0,5) ; 3) \(10^3\) (0,5), valeur de \(c\) (0,5) ; 4) modulo 13 (0,5), modulo 19 (0,5), conclusion (0,5) ; 5) preuve (0,5), rôle de la factorisation (0,25).

Piège classique : réduire l’exposant 173 modulo 247 au lieu de le réduire modulo \(p – 1\) ou \(q – 1\). Les exposants se réduisent modulo l’ordre, jamais modulo le module.

Revenir à l’énoncé du contrôle

Consolider calculs dans Z/nZ et RSA après ce corrigé

Pour ne plus perdre de points sur ce thème, relisez le cours anneaux, idéaux, z/nz et chiffrement rsa ; entraînez-vous sur les exercices anneaux, idéaux, z/nz et chiffrement rsa.

D’autres évaluations corrigées vous attendent sur la page contrôles de maths en L2.

Télécharger en PDF Le livre des 25 contrôles corrigés en L2 PDF à imprimer Voir le livre ›

Télécharger ou imprimer cette fiche «calculs dans Z/nZ et RSA : corrigé du contrôle de maths en L2» au format PDF afin de pouvoir travailler en totale autonomie.

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