Calculs dans Z/nZ et RSA : contrôle de maths en L2
Voici un contrôle de maths en L2 sur le thème « calculs dans Z/nZ et RSA », avec son barème et un corrigé détaillé.
Ce contrôle continu d’une heure trente porte sur l’arithmétique modulaire du semestre 3 de L2 ; il se fait juste après le chapitre sur l’anneau Z/nZ. Le sujet s’ouvre sur une question de cours consacrée aux idéaux de Z, puis il fait étudier les classes inversibles d’un anneau quotient grâce aux divisions successives. Vous démontrerez ensuite le théorème d’Euler afin de réduire des puissances très élevées. Le quatrième exercice demande de résoudre des systèmes de congruences, notamment avec le théorème chinois. Enfin, le problème construit une petite clé RSA, chiffre un message puis le déchiffre sans calculatrice. Aucune notion de groupe abstrait n’est exigée.
Ce qu’évalue le contrôle : calculs dans Z/nZ et RSA
L’essentiel du sujet
- NiveauL2
- Durée1 h 30
- Calculatriceinterdite
- Barèmesur 20
Chapitre : Anneaux, idéaux, Z/nZ et chiffrement RSA (5 exercices)
Ce que ce devoir vérifie :
- Démontrer que tout idéal de Z est principal grâce à la division euclidienne
- Caractériser les classes inversibles de Z/nZ et calculer un inverse par l’algorithme d’Euclide étendu
- Démontrer le théorème d’Euler puis l’utiliser pour réduire de grandes puissances modulo n
- Résoudre un système de congruences, même quand les modules partagent un facteur commun
- Construire une clé RSA, chiffrer un message puis le déchiffrer avec le théorème chinois
Avant de commencer le devoir
Traitez d’abord la question de cours, car la division euclidienne qu’elle utilise revient dans tout le sujet. Pour un inverse modulaire, écrivez les divisions successives puis remontez-les : une relation de Bézout donne aussitôt la réponse. Avant de réduire une puissance, cherchez le plus petit exposant qui donne 1, plutôt que d’appliquer Euler sans réfléchir. Dans le problème, découpez le déchiffrement modulo 13 puis modulo 19. Enfin, vérifiez chaque solution en la remplaçant dans toutes les congruences.
Le sujet du contrôle : calculs dans Z/nZ et RSA
Exercice 1 – Question de cours : les idéaux de Z (3 points)
On rappelle qu’une partie \(I\) de \(\mathbb{Z}\) est un idéal lorsque \((I, +)\) est un sous-groupe de \(\mathbb{Z}\) et que \(ka \in I\) pour tout \(k \in \mathbb{Z}\) et tout \(a \in I\).
- Soit \(n \in \mathbb{N}\). Vérifier que \(n\mathbb{Z}\) est un idéal de \(\mathbb{Z}\).
- Soit \(I\) un idéal de \(\mathbb{Z}\) non réduit à \(\{0\}\). Justifier que \(I\) contient un plus petit élément strictement positif \(n\), puis démontrer que \(I = n\mathbb{Z}\) à l’aide de la division euclidienne.
- On pose \(J = 84\mathbb{Z} + 30\mathbb{Z}\), qui est un idéal de \(\mathbb{Z}\). Trouver deux entiers \(u\) et \(v\) tels que \(84u + 30v = 6\), puis en déduire que \(J = 6\mathbb{Z}\).
Exercice 2 – Le groupe des inversibles de Z/21Z (4 points)
On travaille dans l’anneau \(\mathbb{Z}/21\mathbb{Z}\). La figure place les 21 classes sur un cercle et distingue celles qui sont inversibles.
- Soit \(a \in \mathbb{Z}\). Établir l’équivalence entre l’inversibilité de \(\overline{a}\) dans \(\mathbb{Z}/21\mathbb{Z}\) et la condition \(\mathrm{pgcd}(a, 21) = 1\).
- Calculer l’indicatrice d’Euler \(\varphi(21)\), puis vérifier ce nombre sur la figure.
- Déterminer l’inverse de \(\overline{10}\) par l’algorithme d’Euclide étendu.
- Résoudre l’équation \(x^2 = \overline{1}\) dans \(\mathbb{Z}/21\mathbb{Z}\) en raisonnant modulo 3 puis modulo 7. Que peut-on alors dire de l’intégrité de cet anneau ? Donner deux classes non nulles dont le produit est nul.
Exercice 3 – Théorème d’Euler et grandes puissances (4 points)
Pour \(n \geq 2\), on note \(U_n\) l’ensemble des classes inversibles de \(\mathbb{Z}/n\mathbb{Z}\), qui possède \(\varphi(n)\) éléments.
- Soit \(\overline{a} \in U_n\). Prouver que la multiplication par \(\overline{a}\), à savoir \(\overline{x} \mapsto \overline{a}\,\overline{x}\), permute les éléments de \(U_n\). En calculant de deux façons le produit de tous les éléments de \(U_n\), démontrer alors que \(a^{\varphi(n)} \equiv 1 \ [n]\).
- La figure représente les puissances successives de \(\overline{7}\) dans \(\mathbb{Z}/40\mathbb{Z}\). Calculer \(\varphi(40)\), puis justifier par le calcul les quatre flèches. Comparer ensuite le plus petit exposant \(k \geq 1\) tel que \(7^k \equiv 1 \ [40]\) avec \(\varphi(40)\).
- En déduire le reste de la division euclidienne de \(7^{2026}\) par 40.
- Avec le théorème d’Euler, déterminer le reste de la division de \(13^{403}\) par 50.
Exercice 4 – Congruences simultanées (4 points)
Les deux premières questions portent sur des modules qui ne sont pas premiers entre eux ; le théorème chinois ne s’applique donc pas directement.
- Résoudre dans \(\mathbb{Z}\) le système \(x \equiv 3 \ [6]\) et \(x \equiv 5 \ [8]\).
- Montrer que le système \(x \equiv 1 \ [6]\) et \(x \equiv 2 \ [4]\) n’a aucune solution.
Maëlle compte les jetons d’un jeu de société. Quand elle les range par paquets de 5, il en reste 2 ; par paquets de 7, il en reste 3 ; enfin, par paquets de 9, il en reste 4. Elle sait aussi que la boîte contient entre 400 et 600 jetons.
- Justifier que les deux premières conditions équivalent à \(x \equiv 17 \ [35]\).
- Calculer l’inverse de 8 modulo 9, puis résoudre le système complet modulo 315.
- En déduire le nombre de jetons de la boîte.
Exercice 5 – Problème : une clé RSA de module 247 (5 points)
Gaspard choisit les nombres premiers \(p = 13\) et \(q = 19\), puis il publie la clé \((n, e) = (247, 5)\). Inès veut lui transmettre en secret le message \(m = 10\). Le schéma résume les échanges.
- Calculer \(n = pq\) et \(\varphi(n)\), puis vérifier que \(e = 5\) est premier avec \(\varphi(n)\).
- Déterminer l’exposant secret \(d\), compris entre 1 et \(\varphi(n)\), tel que \(5d \equiv 1 \ [\varphi(n)]\).
- Montrer que le message chiffré vaut \(c = 212\), en calculant d’abord \(10^3\) modulo 247.
- Déchiffrer \(c\) : calculer \(c^d\) modulo 13 puis modulo 19 grâce au petit théorème de Fermat, et conclure avec le théorème chinois.
- Démontrer, pour tout entier \(m\) premier avec \(n\), que \(m^{ed} \equiv m \ [n]\). Pourquoi la connaissance de \(p\) et \(q\) est-elle indispensable pour trouver \(d\) ?
Réviser calculs dans Z/nZ et RSA avant le contrôle
Si un exercice vous a bloqué, 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 avant de retenter le sujet.
La page contrôles de maths en L2 regroupe les 25 sujets de l’année, et la page maths post-bac permet de changer d’année.
Sujets proches à faire ensuite
Télécharger ou imprimer cette fiche «calculs dans Z/nZ et RSA : contrôle de maths en L2» au format PDF afin de pouvoir travailler en totale autonomie.
