Arithmétique
A SAVOIR: le cours sur l'arithmétique
Exercice 3
Un texte est codé à l"aide d'un chiffrement affine selon la méthode suivante.
Les 26 lettres de l'alphabet sont associées à leur indice: A est d'indice 0, B est d'indice 1, ... , Z est d'indice 25.
Chaque lettre d'indice $n$ est remplacée par la lettre dont l'indice est le reste de la division euclidienne de $an+b$ par 26, où $a$ et $b$ sont deux entiers compris entre 0 et 25.
Le texte codé est différent du texte initial, et deux lettres différentes ne peuvent étre codées par la même lettre.
On cherche à déchiffrer un texte codé donné. Ce texte est suffisamment long pour qu'une étude statistique ait permis de conjecturer que A est codé par H, et que E est codé par B.
-
Montrer que $a$ et $b$ vérifient le système
$\{\table 4a+b≡1\,[26];b≡4\,[26]$ - Déterminer tous les couples $(a;b)$ solutions du système, avec $a$ et $b$ entiers compris entre 0 et 25.
- Supposer que $a=18$ et $b=7$ et coder les lettres K et X.
Conclure. - a. Montrer que 5 et 26 sont premiers entre eux.
Déterminer un inverse de 5 modulo 26.
Résoudre $5n≡19\,[26]$
b. Décoder la lettre A.
Corrigé
Clique ICI pour revoir le cours sur la congruence.
- A, d'indice 0, est codé par H, d'indice 7. Donc: $a×0+b≡7\,[26]$, soit: $b≡7\,[26]$.
E, d'indice 4, est codé par B, d'indice 1. Donc: $a×4+b≡1\,[26]$, soit: $4a+b≡1\,[26]$.
Donc $a$ et $b$ vérifient le système
$\{\table 4a+b≡1\,[26];b≡7\,[26]$ -
La seconde ligne donne: $b=26k+7$, avec $k$ entier relatif. Et comme $b$ est un entier compris entre 0 et 25, la seule valeur de $k$ possible est $k=0$.
Donc $b=7$.
D'où: $4a+7≡1\,[26]$, et par là: $4a≡-6\,[26]$, soit: $4a≡20\,[26]$.
Donc: $4a=26k+20$, avec $k$ entier relatif.
Et par là: $2a=13k+10$.
Or on a: soit $k≡0\,[2]$, soit $k≡1\,[2]$.
Si $k≡1\,[2]$, alors: $13k≡13\,[2]$. C'est à dire: $13k≡1\,[2]$. Et donc: $13k+10≡11\,[2]$.
C'est à dire: $2a≡1\,[2]$. Ceci est absurde car $2a$ est pair.
Donc nécessairement, on a: $k≡0\,[2]$.
Et par là: $k=2k'$, avec $k'$ entier relatif.
Et donc, comme $2a=13k+10$, on obtient: $2a=26k+10$, et donc: $a=13k'+5$, avec $k'$ entier relatif.
Et comme $a$ est un entier compris entre 0 et 25, les seules valeurs de $k$ possibles sont $k'=0$, qui donne $a=5$, et $k'=1$, qui donne $a=18$.
Par conséquent, les couples $(a;b)$ solutions du système sont $(5;7)$ et $(18;7)$. - Supposons que $a=18$ et $b=7$.
La lettre K, d'indice 10, est codée par la lettre d'indice 5 (car $18×10+7≡5\,[26]$), c'est à dire F.
La lettre X, d'indice 23, est codée par la lettre d'indice 5 (car $18×23+7≡5\,[26]$), c'est à dire F.
Or deux lettres différentes ne peuvent étre codées par la même lettre.
Donc le couple $(18;7)$ ne convient pas.
Et par élimination, le couple solution est $(5;7)$. - a. On a: $5×(-5)+26×1=1$, donc 5 et 26 sont premiers entre eux, et donc 5 admet un inverse modulo 26.
Comme $5×(-5)+26×1=1$, on a: $5×(-5)=26×1+1$
Et comme $0≤1 < 26$, cela prouve que: $5×(-5)≡1$ $[26]$.
Un inverse de 5 modulo 26 est donc $-5$.
Résolvons l'équation (E) $5n≡19$ $[26]$
(E) $⇔$ $5×(-5)×n≡19×(-5)$ $[26]$ $⇔$ $-25n≡-95$ $[26]$
Or, comme $5×(-5)≡1$ $[26]$, on a: $5×(-5)×n≡1×n$ $[26]$, soit: $-25n≡n$ $[26]$
Et par là, on obtient: (E) $⇔$ $n≡-95$ $[26]$
Soit: (E) $⇔$ $n≡9$ $[26]$
Les solutions cherchées sont donc les nombres de la forme $26k+9$ (où $k$ est un entier relatif).
On peut aussi écrire: $S=\{26k+9, k∈ℤ\}$
b. La lettre A a pour indice 0. On résout donc: $5n+7≡0\,[26]$
Soit: $5n≡-7\,[26]$. Soit: $5n≡19\,[26]$
Donc, d'après le résultat obtenu à la question précédente: $5n≡19\,[26]$ $⇔$ $n≡9$ $[26]$.
Et comme $n$ est un entier compris entre 0 et 25, on a: $n=9$.
Et par là, la lettre codée par un A est la lettre J.