Terminale maths expertes

Arithmétique : nombres premiers et cryptographie — 20 exercices

Cette série étudie les nombres premiers, les factorisations et quelques applications au chiffrement. Le petit théorème de Fermat est énoncé et utilisé explicitement, avec une mise en garde sur sa réciproque fausse. Les exercices cryptographiques distinguent validité mathématique et sécurité réelle : les petits systèmes proposés sont pédagogiques, non utilisables pour protéger des données. Un seul exercice, le dernier, traite de RSA de manière entièrement calculée. Les prolongements sont marqués « Approfondissement ».

L'essentiel à retenir

  • Un nombre premier est un entier au moins égal à 2 ayant exactement deux diviseurs positifs. Le nombre 1 n'est pas premier.
  • Si un entier n≥2n\geq2 est composé, il possède un diviseur premier inférieur ou égal à sa racine carrée. Une preuve de primalité par essais doit donc vérifier tous les premiers jusqu'à cette borne.
  • Tout entier au moins égal à 2 possède une décomposition en facteurs premiers, unique à l'ordre des facteurs près. Cette unicité permet de compter les diviseurs et de tester les carrés parfaits.
  • Si n=p1a1⋯prarn=p_1^{a_1}\cdots p_r^{a_r}, ses diviseurs positifs sont les produits p1b1⋯prbrp_1^{b_1}\cdots p_r^{b_r} avec 0≤bi≤ai0\leq b_i\leq a_i. Leur nombre est (a1+1)⋯(ar+1)(a_1+1)\cdots(a_r+1).
  • Petit théorème de Fermat : si p est premier et si p ne divise pas a, alors ap−1≡1(modp)a^{p-1}\equiv1\pmod p. Pour tout entier a, on a également ap≡a(modp)a^p\equiv a\pmod p.
  • La réciproque du petit théorème de Fermat est fausse : un entier composé peut vérifier une congruence de Fermat pour une base, voire pour toutes les bases premières avec lui.
  • Dans le codage A=0A=0,…,Z=25Z=25, une application affine x↦ax+b(mod26)x\mapsto ax+b\pmod{26} est déchiffrable de manière unique exactement lorsque a est premier avec 26.
  • RSA pédagogique utilise deux premiers distincts p et q, le module n=pq et un exposant e premier avec (p−1)(q−1)(p-1)(q-1). Un inverse d de e modulo ce dernier nombre permet le déchiffrement ; les minuscules paramètres de cette série ne fournissent aucune sécurité.

Exercice 1 — Distinguer premier, composé et cas particuliers

  1. Classer 1, 2, 97 et 221 en justifiant chaque réponse.
  2. Expliquer pourquoi il suffit de tester peu de diviseurs pour 97.
  3. Un élève affirme que tout entier impair est premier : fournir deux contre-exemples de nature différente.
Corrigé détaillé
  1. Le nombre 1 n'est ni premier ni composé : il possède un seul diviseur positif. Le nombre 2 est premier, car ses seuls diviseurs positifs sont 1 et 2 ; c'est le seul premier pair. Pour 97, on a 92<97<1029^2<97<10^2. Il suffit de tester les premiers 2,3,5,7. Il est impair, sa somme de chiffres est 16, il ne finit ni par 0 ni par 5, et 97=7×13+697=7\times13+6. Aucun test ne donne une divisibilité : 97 est premier. Enfin, 221=13×17221=13\times17 est composé.
  2. Si 97 était composé, il aurait un facteur premier inférieur à sa racine carrée, donc inférieur à 10. La liste testée est exhaustive ; vérifier des diviseurs plus grands ne serait pas nécessaire.
  3. Le nombre 9=3² est impair et composé, avec un facteur premier répété. Le nombre 15=3×5 est aussi impair et composé, avec deux facteurs premiers distincts. L'impairité exclut uniquement le facteur 2 ; elle ne garantit nullement l'absence d'autres diviseurs.

Exercice 2 — Factoriser par essais ciblés

  1. Décomposer 1001 et 2024 en facteurs premiers.
  2. En déduire leur PGCD et leur PPCM.
  3. Déterminer si leur produit est un carré parfait et justifier sans calculer ce produit.
Corrigé détaillé
  1. Pour 1001, la division par 7 donne 1001=7×1431001=7\times143, puis 143=11×13143=11\times13. Les trois facteurs 7,11,13 sont premiers : 1001=7×11×131001=7\times11\times13. Pour 2024, on extrait les facteurs 2 : 2024=2×1012=22×506=23×2532024=2\times1012=2^2\times506=2^3\times253, puis 253=11×23253=11\times23. Ainsi 2024=23×11×232024=2^3\times11\times23.
  2. Le seul facteur premier commun est 11, avec exposant minimal 1 : le PGCD vaut 11. Pour le PPCM, on conserve chaque facteur avec l'exposant maximal : 23×7×11×13×232^3\times7\times11\times13\times23. Numériquement, cela vaut 184184. On vérifie également (1001×2024)/11=91×2024=184184(1001\times2024)/11=91\times2024=184184.
  3. Le produit a pour décomposition 23×7×112×13×232^3\times7\times11^2\times13\times23. Un carré parfait doit avoir tous ses exposants premiers pairs. Les exposants de 2,7,13 et 23 sont impairs ; le produit n'est donc pas un carré. La taille du produit n'intervient pas : seule la parité des exposants compte.

Exercice 3 — Compter et classer les diviseurs

  1. Décomposer 360 et compter ses diviseurs positifs.
  2. Déterminer combien de ces diviseurs sont pairs et combien sont des carrés parfaits.
  3. Donner la liste complète des diviseurs carrés.
Corrigé détaillé
  1. On a 360=36×10=23×32×5360=36\times10=2^3\times3^2\times5. Un diviseur positif s'écrit de manière unique 2a3b5c2^a3^b5^c, avec a∈{0,1,2,3}, b∈{0,1,2} et c∈{0,1}. Le nombre total est donc 4×3×2=244\times3\times2=24.
  2. Un diviseur est pair exactement lorsque a≥1a\geq1. Il y a alors trois choix pour a, trois pour b et deux pour c : cela donne 18 diviseurs pairs. Les six autres sont impairs, ce qui vérifie le total. Pour obtenir un carré, chaque exposant doit être pair : a peut valoir 0 ou 2, b peut valoir 0 ou 2, et c doit valoir 0. Il y a donc 2×2×1=42\times2\times1=4 diviseurs carrés.
  3. Les choix d'exposants donnent 11, 22=42^2=4, 32=93^2=9 et 22×32=362^2\times3^2=36. Tous divisent effectivement 360 : les quotients sont 360,90,40 et 10. Il serait incorrect d'inclure 25, car la décomposition de 360 ne contient qu'un seul facteur 5, alors que 25 en exige deux.

Exercice 4 — Un grand carré caché dans un entier

  1. Décomposer 7560 en facteurs premiers.
  2. Trouver le plus grand carré parfait qui le divise et simplifier 7560\sqrt{7560}.
  3. Déterminer le plus petit entier positif k tel que 7560k soit un carré parfait.
Corrigé détaillé
  1. On extrait les facteurs successifs : 7560=8×9457560=8\times945, puis 945=27×35945=27\times35. Ainsi 7560=23×33×5×77560=2^3\times3^3\times5\times7.
  2. Pour construire le plus grand diviseur carré, on choisit les plus grands exposants pairs inférieurs ou égaux aux exposants disponibles. On obtient 22×32=362^2\times3^2=36. En effet, 7560=36×2107560=36\times210, et 210=2×3×5×7 n'a aucun facteur carré supérieur à 1. Par conséquent, 7560=6210\sqrt{7560}=6\sqrt{210}, forme simplifiée.
  3. Les quatre exposants de 2,3,5,7 sont impairs. Il faut apporter au moins un facteur de chacun de ces premiers pour les rendre pairs. Le plus petit choix est donc k=2×3×5×7=210k=2\times3\times5\times7=210. Alors 7560×210=24×34×52×72=(4×9×5×7)2=12602=15876007560\times210=2^4\times3^4\times5^2\times7^2=(4\times9\times5\times7)^2=1260^2=1587600. Tout multiplicateur convenable doit contenir ces quatre facteurs premiers au moins une fois ; cela prouve la minimalité de 210.

Exercice 5 — Une factorisation par différence de carrés

  1. Factoriser 10403 en le comparant à 102².
  2. Justifier que la factorisation obtenue est une décomposition en nombres premiers.
  3. Donner tous les diviseurs positifs de 10403 et leur somme.
Corrigé détaillé
  1. On calcule 1022=10404102^2=10404, donc 10403=1022−1=(102−1)(102+1)=101×10310403=102^2-1=(102-1)(102+1)=101\times103. L'identité de différence de carrés évite une longue recherche de diviseurs.
  2. Les racines carrées de 101 et 103 sont comprises entre 10 et 11 ; les seuls premiers à tester sont 2,3,5,7. Les deux nombres sont impairs, leurs sommes de chiffres valent 2 et 4, et aucun ne finit par 0 ou 5. Enfin, 101=7×14+3101=7\times14+3 et 103=7×14+5103=7\times14+5. Aucun n'est divisible par 7. Ils sont donc tous deux premiers.
  3. Comme les deux facteurs sont premiers distincts, les diviseurs positifs sont 1,101,103 et 10403. Leur somme vaut 1+101+103+10403=106081+101+103+10403=10608. On peut la retrouver sous la forme (1+101)(1+103)=102×104=10608(1+101)(1+103)=102\times104=10608. Le nombre de diviseurs est (1+1)(1+1)=4(1+1)(1+1)=4, conformément à la liste. La factorisation seule ne dispensait pas de contrôler la primalité de 101 et de 103.

Exercice 6 — Le petit théorème de Fermat en action

  1. Énoncer le petit théorème de Fermat et vérifier ses hypothèses pour la base 2 et le module 13.
  2. Calculer le reste de 210002^{1000} modulo 13.
  3. Déterminer le reste de 21000+5122^{1000}+5^{12} modulo 13.
Corrigé détaillé
  1. Si p est premier et si a n'est pas divisible par p, alors ap−1≡1(modp)a^{p-1}\equiv1\pmod p. Ici, 13 est premier et 13 ne divise pas 2, donc 212≡1(mod13)2^{12}\equiv1\pmod{13}. Il faut énoncer les deux hypothèses : le seul fait d'avoir un module entier ne suffit pas.
  2. La division de l'exposant donne 1000=12×83+41000=12\times83+4. Ainsi 21000=(212)8324≡183×16≡3(mod13)2^{1000}=(2^{12})^{83}2^4\equiv1^{83}\times16\equiv3\pmod{13}. Le reste est 3.
  3. Le nombre 5 est également premier avec 13, donc Fermat donne 512≡1(mod13)5^{12}\equiv1\pmod{13}. La somme est congrue à 3+1=4 : son reste est 4. Le théorème réduit ici les exposants modulo 12, et non modulo 13. Cette distinction est essentielle : le module concerne les valeurs des puissances, tandis que p-1 intervient comme période possible des exposants pour les bases non nulles modulo p.

Exercice 7 — Approfondissement — Pourquoi Fermat fonctionne

Soit p un nombre premier et a un entier non divisible par p.
  1. Montrer que les restes de a,2a,…,(p-1)a sont une permutation de 1,2,…,p-1.
  2. En déduire le petit théorème de Fermat.
  3. Expliquer pourquoi la simplification finale est licite.
Corrigé détaillé
  1. Aucun produit ka, pour 1≤k≤p-1, n'est nul modulo p : sinon p diviserait ka et, comme il ne divise pas a, il diviserait k, impossible. Si ia et ja ont le même reste, alors p∣a(i−j)p\mid a(i-j). Le lemme de Gauss donne p∣(i−j)p\mid(i-j). Or |i-j|<p, donc i=j. On a p-1 restes distincts, tous non nuls : ils forment exactement l'ensemble annoncé.
  2. En multipliant tous ces restes, on obtient ap−1(p−1)!≡(p−1)!(modp)a^{p-1}(p-1)!\equiv(p-1)!\pmod p. En simplifiant le facteur factoriel, il vient ap−1≡1(modp)a^{p-1}\equiv1\pmod p.
  3. Aucun des facteurs 1,…,p-1 n'est divisible par p. Comme p est premier, il ne divise pas leur produit ; le PGCD de (p-1)! et p vaut donc 1. Le produit possède un inverse modulo p, ce qui autorise la simplification. Cette étape n'est pas une division ordinaire dans les entiers : c'est une multiplication par un inverse modulaire. Sans coprimalité, une simplification de congruence pourrait modifier le module ou perdre l'équivalence.

Exercice 8 — La réciproque de Fermat est fausse

  1. Montrer que 341 est composé.
  2. Vérifier que 2340≡1(mod341)2^{340}\equiv1\pmod{341} sans calculer la puissance entière.
  3. Expliquer ce que ce résultat permet, et ne permet pas, de conclure dans un test de primalité.
Corrigé détaillé
  1. On a 341=11×31341=11\times31, donc 341 est composé. Les facteurs sont supérieurs à 1.
  2. On calcule seulement 210=1024=3×341+12^{10}=1024=3\times341+1. Par conséquent, 210≡1(mod341)2^{10}\equiv1\pmod{341}. Comme 340=34×10, on obtient 2340=(210)34≡1(mod341)2^{340}=(2^{10})^{34}\equiv1\pmod{341}. Le nombre 341 vérifie donc la conclusion d'une congruence de Fermat pour la base 2, tout en étant composé.
  3. Si un entier n≥2n\geq2, premier avec 22, ne vérifie pas 2n−1≡1(modn)2^{n-1}\equiv1\pmod n, alors il n'est pas premier : c'est une utilisation correcte de la contraposée du théorème. En revanche, satisfaire la congruence ne prouve pas la primalité. On appelle 341 un nombre pseudopremier en base 2. Le contre-exemple ne contredit pas Fermat, dont l'implication part de l'hypothèse « n est premier ». Il réfute uniquement la réciproque. Un test fondé sur une seule base peut donc éliminer certains composés, mais ne constitue pas en général un certificat de primalité.

Exercice 9 — Approfondissement — Un composé trompe toutes les bases admissibles

  1. Décomposer 561 en facteurs premiers.
  2. Montrer que a560≡1(mod561)a^{560}\equiv1\pmod{561} pour tout entier a premier avec 561.
  3. Expliquer pourquoi cette propriété n'affirme rien de tel pour a=3a=3.
Corrigé détaillé
  1. La somme des chiffres de 561 vaut 12, donc 3 le divise : 561=3×187=3×11×17561=3\times187=3\times11\times17. Ces facteurs sont premiers et distincts.
  2. Si a est premier avec 561, il n'est divisible ni par 3, ni par 11, ni par 17. Fermat donne respectivement a2≡1(mod3)a^2\equiv1\pmod3, a10≡1(mod11)a^{10}\equiv1\pmod{11} et a16≡1(mod17)a^{16}\equiv1\pmod{17}. Or 560=2×280=10×56=16×35560=2\times280=10\times56=16\times35. Ainsi a^560 est congru à 1 modulo chacun des trois facteurs. Leur coprimalité deux à deux implique que 561 divise a^560-1. On a démontré la congruence pour toutes les bases admissibles, malgré la composition de 561 : c'est un exemple de nombre de Carmichael.
  3. Pour a=3a=3, le PGCD avec 561 vaut 3 ; l'hypothèse est fausse. De fait, 3560≡0(mod3)3^{560}\equiv0\pmod3, donc cette puissance ne peut être congrue à 1 modulo 561. La restriction aux bases premières avec le module est indispensable, aussi bien dans Fermat que dans la propriété établie ici.

Exercice 10 — Démontrer l'infinitude des nombres premiers

  1. Présenter une preuve par contradiction de l'infinitude des nombres premiers.
  2. Appliquer la construction à la liste 2,3,5,7 et factoriser le nombre obtenu.
  3. Expliquer pourquoi la preuve n'exige pas que le nombre construit soit premier.
Corrigé détaillé
  1. Supposons qu'il n'existe qu'un nombre fini de premiers, notés p1p_1,…,prp_r. Considérons N=p1⋯pr+1N=p_1\cdots p_r+1, qui est supérieur à 1. Il possède au moins un diviseur premier q. Pour chaque indice i, N a pour reste 1 modulo pip_i ; aucun des pip_i ne le divise. Le premier q est donc absent de la liste, contradiction. Il existe une infinité de nombres premiers.
  2. Pour 2,3,5,7, le produit vaut 210 et N=211N=211. Sa racine carrée est comprise entre 14 et 15. Les premiers à tester sont 2,3,5,7,11,13. Les trois premiers tests sont immédiats ; puis 211=7×30+1=11×19+2=13×16+3211=7\times30+1=11\times19+2=13\times16+3. Aucun ne divise 211 : ce nombre est lui-même premier.
  3. Le rôle de N est de posséder un facteur premier nouveau, pas nécessairement d'être premier. Même si N était composé, chacun de ses facteurs premiers serait absent de la liste initiale. Confondre ces deux affirmations transforme une preuve correcte en une proposition fausse sur les nombres « produit des premiers plus 1 ».

Exercice 11 — La factorielle plus un n'est pas toujours première

  1. Montrer que, pour n≥2n\geq2, aucun entier de 2 à n ne divise n!+1.
  2. Réfuter l'affirmation « n!+1 est toujours premier » avec n=5n=5.
  3. Déterminer la plus petite valeur de n≥2n\geq2 pour laquelle l'affirmation échoue.
Corrigé détaillé
  1. Si 2≤d≤n, alors d est l'un des facteurs de n!, donc n!≡0(modd)n!\equiv0\pmod d. On a alors n!+1≡1(modd)n!+1\equiv1\pmod d, ce qui exclut la divisibilité par d.
  2. Pour n=5n=5, 5!+1=120+1=121=1125!+1=120+1=121=11^2. Le nombre est composé, bien qu'il n'ait aucun diviseur entre 2 et 5. Ses facteurs premiers peuvent être strictement supérieurs à n.
  3. Il faut vérifier les valeurs précédentes : 2!+1=32!+1=3, 3!+1=73!+1=7, 4!+1=254!+1=25. Le nombre 25=5² est déjà composé. La plus petite valeur est donc n=4n=4, et non n=5n=5. La question 2 demandait un contre-exemple particulier ; elle ne prétendait pas qu'il soit minimal. Cet exercice souligne deux limites : exclure une petite liste de diviseurs n'établit pas la primalité si la liste n'atteint pas la racine carrée, et fournir un contre-exemple ne suffit pas à démontrer qu'il est le premier. Pour 25, le facteur 5 dépasse n=4n=4 mais atteint exactement la racine carrée.

Exercice 12 — Construire une longue suite de nombres composés

  1. Démontrer que les nombres 7!+2,7!+3,…,7!+77!+2,7!+3,\ldots,7!+7 sont tous composés.
  2. Donner leurs valeurs et un diviseur propre de chacun.
  3. Généraliser à une suite de L entiers consécutifs composés, pour L≥1L\geq1.
Corrigé détaillé
  1. Pour chaque k entre 2 et 7, k divise 7!, donc il divise 7!+k. De plus, 7!+k>k>17!+k>k>1 : k est un diviseur propre, ce qui prouve la composition. Les six nombres sont consécutifs puisque k augmente de 1.
  2. Comme 7!=5040, on obtient 5042,5043,5044,5045,5046,5047. Des diviseurs propres respectifs sont 2,3,4,5,6,7. On peut vérifier les quotients : 2521,1681,1261,1009,841,721. Les diviseurs 4 et 6 n'ont pas besoin d'être premiers : exhiber n'importe quel diviseur strictement compris entre 1 et le nombre suffit à établir qu'il est composé.
  3. Posons M=(L+1)!. Les L entiers M+2,M+3,…,M+(L+1)M+2,M+3,\ldots,M+(L+1) sont consécutifs. Le terme M+k est divisible par k pour chaque k de 2 à L+1, et il est strictement supérieur à k. Ils sont donc tous composés. On prouve ainsi qu'il existe des intervalles sans nombre premier de longueur arbitrairement grande, sans affirmer qu'il n'existe qu'un nombre fini de premiers.

Exercice 13 — Nombres de Mersenne : condition nécessaire, non suffisante

  1. Montrer que si n=ab avec a,b>1b>1, alors 2n−12^n-1 est composé.
  2. En déduire une condition nécessaire pour que 2n−12^n-1 soit premier.
  3. Montrer que cette condition n'est pas suffisante en étudiant n=11n=11.
Corrigé détaillé
  1. La différence de puissances se factorise : 2ab−1=(2a−1)(1+2a+22a+⋯+2a(b−1))2^{ab}-1=(2^a-1)(1+2^a+2^{2a}+\cdots+2^{a(b-1)}). Comme a>1a>1, le premier facteur vaut au moins 3. Comme b>1b>1, le second possède au moins deux termes positifs et vaut au moins 1+2a2^a>1. On a donc deux facteurs strictement supérieurs à 1 : le nombre est composé.
  2. Si n≥2n\geq2 et si 2n−12^n-1 est premier, n ne peut pas être composé ; n doit être premier. Le cas n=1n=1 donne 1, qui n'est pas premier.
  3. L'exposant 11 est premier, mais 211−1=2048−1=2047=23×892^{11}-1=2048-1=2047=23\times89. La multiplication donne bien 23×89=23(90−1)=2070−23=204723\times89=23(90-1)=2070-23=2047. Les deux facteurs sont supérieurs à 1 ; le nombre de Mersenne est donc composé. La proposition correcte est « primalité du nombre de Mersenne implique primalité de l'exposant », et non une équivalence. La factorisation de la question 1 ne détecte pas ce contre-exemple, puisque son exposant n'est pas composé.

Exercice 14 — Approfondissement — Une restriction sur les nombres de Fermat

  1. Montrer que si n possède un diviseur impair d>1d>1, alors 2n+12^n+1 est composé.
  2. En déduire que la primalité de 2n+12^n+1, pour n≥1n\geq1, impose que n soit une puissance de 2.
  3. Vérifier que les exposants 1,2,4 donnent des nombres premiers et expliquer la portée limitée de cette vérification.
Corrigé détaillé
  1. Écrivons n=dm, avec d impair et d>1d>1, et posons x=2m2^m≥2. Pour un exposant impair, xd+1=(x+1)(xd−1−xd−2+⋯−x+1)x^d+1=(x+1)(x^{d-1}-x^{d-2}+\cdots-x+1). Le premier facteur est supérieur à 1. Le quotient est également supérieur à 1, car xd+1>x+1x^d+1>x+1 lorsque d≥3d\geq3 et x≥2x\geq2. Le nombre est donc composé.
  2. Tout entier positif s'écrit n=2t2^t u avec u impair. Si u>1u>1, la question précédente exclut la primalité. Il faut donc u=1u=1, soit n=2t2^t.
  3. Pour n=1n=1,2,4, on obtient 3,5,17. Les deux premiers sont immédiatement premiers. Pour 17, les seuls premiers inférieurs à sa racine carrée sont 2 et 3, qui ne le divisent pas. Ces trois exemples vérifient la condition nécessaire et donnent effectivement des premiers, mais ils ne prouvent pas que toutes les puissances de 2 comme exposants fonctionnent. Une condition nécessaire ne devient pas suffisante parce que quelques premières valeurs la satisfont.

Exercice 15 — Approfondissement — Une factorisation remarquable

  1. Démontrer l'identité a4+4=(a2−2a+2)(a2+2a+2)a^4+4=(a^2-2a+2)(a^2+2a+2).
  2. Déterminer les entiers positifs a pour lesquels a4+4a^4+4 peut être premier.
  3. Appliquer la factorisation à a=3a=3 et a=10a=10.
Corrigé détaillé
  1. On réécrit a4+4=(a2+2)2−(2a)2a^4+4=(a^2+2)^2-(2a)^2. La différence de carrés donne exactement les deux facteurs demandés. On peut aussi développer : (a2+2)2−4a2=a4+4(a^2+2)^2-4a^2=a^4+4.
  2. Le premier facteur vaut (a−1)2+1(a-1)^2+1 ; il est égal à 1 seulement pour a=1a=1. Pour tout a≥2a\geq2, il est au moins 2, et le second facteur (a+1)2+1(a+1)^2+1 est également supérieur à 1. Le nombre est alors composé. Pour a=1a=1, on obtient 1⁴+4=5, qui est premier. La seule valeur positive convenable est donc a=1a=1.
  3. Pour a=3a=3, les facteurs valent 9−6+2=59-6+2=5 et 9+6+2=179+6+2=17, donc 34+4=85=5×173^4+4=85=5\times17. Pour a=10a=10, ils valent 82 et 122, donc 104+4=10004=82×12210^4+4=10004=82\times122. En poursuivant, 82=2×4182=2\times41 et 122=2×61122=2\times61, d'où 10004=22×41×6110004=2^2\times41\times61. Les nombres 41 et 61 sont premiers, ce que l'on vérifie en testant 2,3,5 pour 41, et 2,3,5,7 pour 61.

Exercice 16 — Un chiffrement affine valide

On code A=0A=0,…,Z=25Z=25 et on chiffre par E(x)≡5x+8(mod26)E(x)\equiv5x+8\pmod{26}.
  1. Justifier que le chiffrement est réversible et établir la formule de déchiffrement.
  2. Chiffrer BONJOUR.
  3. Vérifier le déchiffrement des trois premières lettres chiffrées.
Corrigé détaillé
  1. Le PGCD de 5 et 26 vaut 1, donc 5 est inversible modulo 26. Son inverse est 21, car 5×21=105=4×26+15\times21=105=4\times26+1. À partir de y≡5x+8, on obtient x≡21(y−8)(mod26)x\equiv21(y-8)\pmod{26}. Comme -168≡14 modulo 26, on peut aussi écrire D(y)≡21y+14(mod26)D(y)\equiv21y+14\pmod{26}.
  2. BONJOUR correspond à 1,14,13,9,14,20,17. Les valeurs de 5x+8 sont 13,78,73,53,78,108,93 ; leurs restes modulo 26 sont 13,0,21,1,0,4,15. Les lettres obtenues sont N,A,V,B,A,E,P : le texte chiffré est NAVBAEP.
  3. Pour N, y=13y=13 et 21(13−8)=105≡121(13-8)=105\equiv1, donc B. Pour A, y=0y=0 et 21(0−8)=−168≡1421(0-8)=-168\equiv14, donc O. Pour V, y=21y=21 et 21(21−8)=273≡1321(21-8)=273\equiv13, donc N. La réversibilité est exacte, mais ce système reste très faible : il conserve notamment les répétitions de lettres et possède un petit nombre de clés possibles.

Exercice 17 — Un chiffrement affine non valide

On propose E(x)≡2x+4(mod26)E(x)\equiv2x+4\pmod{26}.
  1. Montrer que deux lettres différentes peuvent avoir la même image.
  2. Déterminer exactement les messages d'une lettre pouvant produire le code 4, puis le code 5.
  3. Décrire l'ensemble des codes atteignables et expliquer pourquoi aucun déchiffrement unique n'existe.
Corrigé détaillé
  1. Les codes 0 et 13, correspondant à A et N, donnent E(0)≡4E(0)\equiv4 et E(13)≡30≡4(mod26)E(13)\equiv30\equiv4\pmod{26}. Deux lettres différentes produisent donc E. Plus généralement, E(x+13)−E(x)=26E(x+13)-E(x)=26, donc les lettres séparées de 13 positions sont toujours confondues.
  2. Pour obtenir le code 4, on résout 2x+4≡4(mod26)2x+4\equiv4\pmod{26}, soit 2x≡0(mod26)2x\equiv0\pmod{26}. En divisant par 2 avec le module, on obtient x≡0x\equiv0 modulo 13 : dans 0,…,25, les solutions sont 0 et 13, donc A et N. Pour obtenir le code 5, il faudrait 2x≡1(mod26)2x\equiv1\pmod{26}, impossible par parité.
  3. Toutes les valeurs 2x+4 sont paires, et l'on atteint exactement les treize restes pairs 0,2,4,…,24. Chacun possède deux antécédents parmi les 26 lettres. Le PGCD de 2 et 26 vaut 2, non 1 : le coefficient multiplicatif n'a pas d'inverse. Le système n'est ni injectif ni surjectif sur l'alphabet et ne permet donc pas un déchiffrement univoque.

Exercice 18 — Retrouver une clé affine à partir de deux correspondances

Un chiffrement affine E(x)≡ax+b(mod26)E(x)\equiv ax+b\pmod{26} transforme C en R et F en G.
  1. Retrouver a et b modulo 26.
  2. Vérifier que la clé est valide et donner le déchiffrement.
  3. Déchiffrer la lettre Z.
Corrigé détaillé
  1. Les codes sont C=2C=2, R=17R=17, F=5F=5 et G=6G=6. Les informations donnent 2a+b≡172a+b\equiv17 et 5a+b≡6(mod26)5a+b\equiv6\pmod{26}. En soustrayant, 3a≡−11≡15(mod26)3a\equiv-11\equiv15\pmod{26}. L'inverse de 3 est 9, car 27≡1 modulo 26. Ainsi a≡9×15=135≡5a\equiv9\times15=135\equiv5. Puis b≡17−2×5=7b\equiv17-2\times5=7. La clé est donc (a,b)=(5,7) modulo 26.
  2. Le PGCD de 5 et 26 vaut 1 : le chiffrement est valide. L'inverse de 5 étant 21, le déchiffrement est D(y)≡21(y−7)(mod26)D(y)\equiv21(y-7)\pmod{26}. Vérification des données : 5×2+7=175\times2+7=17 et 5×5+7=32≡65\times5+7=32\equiv6.
  3. Z a pour code 25. On calcule 21(25−7)=21×18=378=14×26+1421(25-7)=21\times18=378=14\times26+14. Le code clair est 14, soit O. En rechiffrant O, on obtient 5×14+7=77≡255\times14+7=77\equiv25, donc Z. Deux correspondances ont suffi ici parce que la différence des codes clairs, 3, était inversible modulo 26.

Exercice 19 — Combien d’itérations pour annuler un chiffrement multiplicatif ?

On code par les classes modulo 2929 et on définit E(x)≡3x(mod29)E(x)\equiv3x\pmod{29}.
  1. Expliquer pourquoi le chiffrement est bijectif et donner son inverse.
  2. Déterminer le plus petit entier k>0k>0 tel que Ek(x)=xE^k(x)=x pour tous les codes.
  3. Déterminer les codes fixes de EE.
Corrigé détaillé
1. 3×10=30≡1(mod29)3\times10=30\equiv1\pmod{29}, donc E−1(y)≡10y(mod29)E^{-1}(y)\equiv10y\pmod{29}. 2. Ek(x)≡3kxE^k(x)\equiv3^kx ; l’égalité pour tous les codes équivaut à 3k≡13^k\equiv1, en prenant x=1x=1. Fermat donne 328≡13^{28}\equiv1. Les calculs donnent 32≡93^2\equiv9, 34≡233^4\equiv23, 37≡123^7\equiv12 et 314≡−13^{14}\equiv-1. Aucun des diviseurs propres 1,2,4,7,141,2,4,7,14 de 2828 ne convient. La période minimale divise 2828 par division euclidienne des exposants ; elle vaut donc 2828. 3. 3x≡x3x\equiv x donne 2x≡0(mod29)2x\equiv0\pmod{29}. Comme 22 est inversible, seul le code 00 est fixe. Tous les codes reviennent après 2828 itérations, mais seul zéro revient après une.

Exercice 20 — Approfondissement — Un unique exemple RSA entièrement calculé

On prend p=61p=61, q=53q=53 et e=17e=17.
  1. Construire les clés RSA en calculant n, φ(n) et l'exposant privé d.
  2. Chiffrer le message entier m=65m=65 par exponentiation rapide.
  3. Déchiffrer le résultat avec les réductions modulo 61 et 53, puis expliquer pourquoi cet exemple n'offre aucune sécurité réelle.
Corrigé détaillé
  1. Les nombres 61 et 53 sont premiers : les seuls premiers à tester jusqu'à leurs racines carrées sont 2,3,5,7, et aucun ne les divise. On calcule n=61×53=3233n=61\times53=3233 et φ(n)=60×52=3120\varphi(n)=60\times52=3120. Euclide donne 3120=17×183+93120=17\times183+9, 17=9+817=9+8, 9=8+19=8+1. En remontant, 1=9−8=2×9−17=2×3120−367×171=9-8=2\times9-17=2\times3120-367\times17. L'inverse de 17 modulo 3120 est donc d=−367d=-367+3120=2753. Vérification : 17×2753=46801=15×3120+117\times2753=46801=15\times3120+1. La clé publique est (3233,17), et l'exposant privé est 2753.
  2. Le message vérifie 0≤65<3233. On calcule modulo 3233 : 652=4225≡99265^2=4225\equiv992 ; 654≡9922=984064≡123265^4\equiv992^2=984064\equiv1232 ; 658≡12322=1517824≡154765^8\equiv1232^2=1517824\equiv1547 ; 6516≡15472=2393209≡78965^{16}\equiv1547^2=2393209\equiv789. Les divisions correspondantes sont 984064=3233×304+1232984064=3233\times304+1232, 1517824=3233×469+15471517824=3233\times469+1547 et 2393209=3233×740+7892393209=3233\times740+789. Comme 17=16+1, c≡789×65=51285≡2790(mod3233)c\equiv789\times65=51285\equiv2790\pmod{3233}, car 51285=3233×15+279051285=3233\times15+2790. Le chiffré est donc c=2790c=2790.
  3. On veut calculer c^2753 modulo 3233. Comme 2790≡45≢0(mod61)2790\equiv45\not\equiv0\pmod{61} et 2790≡34≢0(mod53)2790\equiv34\not\equiv0\pmod{53}, Fermat autorise les réductions des exposants modulo 6060 et 5252. Modulo 61, c≡45c\equiv45 et 2753≡53 modulo 60. Les carrés donnent 452≡1245^2\equiv12, 454≡2245^4\equiv22, 458≡5745^8\equiv57, 4516≡1645^{16}\equiv16, 4532≡1245^{32}\equiv12. Puisque 53=32+16+4+1, le produit des restes vaut 12×16×22×4512\times16\times22\times45. En réduisant : 12×16≡9, 9×22≡15 et 15×45≡4 modulo 61. Le déchiffré vaut donc 4 modulo 61. Modulo 53, c≡34c\equiv34 et 2753≡49 modulo 52. On obtient 342≡4334^2\equiv43, 344≡4734^4\equiv47, 348≡3634^8\equiv36, 3416≡2434^{16}\equiv24, 3432≡4634^{32}\equiv46. Comme 49=32+16+1, on multiplie : 46×24=1104≡4446\times24=1104\equiv44, puis 44×34=1496≡12(mod53)44\times34=1496\equiv12\pmod{53}. Le déchiffré x vérifie donc x≡4x\equiv4 modulo 61 et x≡12x\equiv12 modulo 53. Écrivons x=4+61kx=4+61k ; modulo 53, cela donne 4+8k≡124+8k\equiv12, donc 8k≡8 et k≡1k\equiv1 modulo 53. Ainsi x≡65x\equiv65 modulo 3233. Dans l'intervalle de messages 0,…,3232, on retrouve exactement m=65m=65. La correction vient aussi de ed≡1 modulo 60 et modulo 52, puis de Fermat sur chacun des facteurs premiers ; pour un message divisible par l'un d'eux, la congruence correspondante est simplement nulle. Cet exemple est uniquement pédagogique : 3233 se factorise immédiatement, et le RSA brut sans encodage sécurisé ne convient pas à la protection de messages réels.

Besoin d'aide sur ce chapitre ?

Réserver le bilan offert de 30 minSoutien Maths expertes