On considère les dix caractères A, B, C, D, E, F, G, H, I et J auxquels on associe dans l’ordre les nombres entiers de 1 à 10. On note $\Omega$= {1, 2, . . . , 10}. On appelle message tout mot, ayant un sens ou non, formé avec ces dix caractères.
1. On désigne par f la fonction définie sur $\Omega$ par « f(n) est le reste de la division euclidienne de $5^n$ par 11 ».
On désire coder à l’aide de f le message « BACF ». Compléter la grille de chiffrement ci-dessous :
| Lettre |
B |
A |
C |
F |
| n |
2 |
1 |
3 |
6 |
| f(n) |
3 |
|
|
|
| Lettre |
C |
|
|
|
Peut-on déchiffrer le message codé avec certitude ?
2. On désigne par g la fonction définie sur $\Omega$ par « g(n) est le reste de la division euclidienne de $2^n$ par 11 ». Établir, sur le modèle précédent, la grille de chiffrement de g. Permet-elle le déchiffrement avec certitude de tout message codé à l’aide de g ?
3. Le but de cette question est de déterminer des conditions sur l’entier a compris entre 1 et 10 pour que la fonction h définie sur E par « h(n) est le reste de la division euclidienne de $a^n$ par 11 » permette de chiffrer et déchiffrer avec certitude un message de 10 caractères.
Soit i un élément de $\Omega$.
a. Montrer, en raisonnant par l’absurde, que si, pour tout , i < 10, $a^i$ n’est pas congru à 1 modulo 11, alors la fonction h permet le déchiffrement avec certitude de tous messages.
b. Montrer que s’il existe $i \in{\Omega}$, i < 10, tel que $a^i \equiv{1}[11]$, alors la fonction h ne permet pas de déchiffrer un message avec certitude.
c. On suppose que i est le plus petit entier naturel tel que vérifiant $a^i \equiv{1}[11]$.
En utilisant la division euclidienne de 10 par i, prouver que i est un diviseur de 10.
d. Quelle condition doit vérifier le nombre a pour permettre le chiffrage et le déchiffrage sans ambiguïté de tous messages à l’aide de la fonction h ? Faire la liste de ces nombres.
Correction :
1. Le tableau est obtenu en conservant le reste de la division euclidienne de $5^k$, $k \in{\{1;…;10}\}$ par $11$ :
| Lettre |
B |
A |
C |
F |
| n |
2 |
1 |
3 |
6 |
| f(n) |
3 |
5 |
4 |
5 |
| Lettre |
C |
E |
D |
E |
A et F donnent E. Autrement dit, E a plusieurs antécédents, on ne peut donc pas déchiffrer un message sans ambiguïté.
2. De manière analogue à la première question, le tableau est obtenu en conservant le reste de la division euclidienne de $2^k$, $k \in{\{1;…;10}\}$ par $11$ :
| Lettre |
A |
B |
C |
D |
E |
F |
G |
H |
I |
J |
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| f(n) |
2 |
4 |
8 |
5 |
10 |
9 |
7 |
3 |
6 |
1 |
| Lettre |
B |
D |
H |
E |
J |
I |
G |
C |
F |
A |
Chaque lettre a un antécédent unique, on peut donc déchiffrer tout message avec certitude
3a. on suppose que pour tout $a\in{\{1;…;10}\}$ et que pour tout $i<10$, on a $a^i \not\equiv{1} [11]$ et qu’il existe deux entiers naturels i, j avec $1\leq j<i<10$ tels que $a^j \equiv a^i [11]$ (deux lettres ont la même image)
On a $a^j \equiv a^i [11] \Leftrightarrow a^j – a^i\equiv 0 [11] \Leftrightarrow a^j (1- a^{i-j}) \equiv 0 [11]$ or $11$ étant un nombre premier l’anneau $\mathbb Z /11\mathbb Z$ est intègre c’est à dire : $a^j\equiv{0} [11]$ ou $(1- a^{i-j})\equiv{0} [11]$
Or $a \in{\{1;…;10}\}$ , et $11$ premier, $a^j$ ne peut être un multiple de 11 donc $(1- a^{i-j})\equiv{0} [11]$
soit $a^{i-j}\equiv{1} [11]$ avec $i-j<10$ ce qui contredit l’hypothèse.
3b. on suppose qu’il existe $i \in{\{1;..;10}\}$ tel que $a^i \equiv{1} [11]$
D’après le petit théorème de Fermat, 11 étant premier on a l’égalité suivante : $a^{11-1} \equiv{1} [11]$ $\Leftrightarrow $ $a^{10}\equiv{1} [11]$ $\Leftrightarrow $ $a^i.a^{10-i}\equiv{1} [11]$ or $a^i \equiv{1} [11]$ donc $a^{10-i}\equiv{1} [11]$ ainsi 2 lettres ont la même image, on ne peut donc pas déchiffrer les messages avec certitude.
3c. D’après la division euclidienne de 10 par i, il existe q et r entiers tel que : $10=qi+r$
on a toujours d’après le petit théorème de Fermat (11 premier) : $a^{10}\equiv{1} [11]$ $\Leftrightarrow$ $a^{qi+r} \equiv{1} [11]$ $\Leftrightarrow$ $a^{q.i}.a^r\equiv{1} [11]$ $\Leftrightarrow$ $(a^i)^q.a^r\equiv{1} [11]$ or $a^i \equiv{1} [11]$ donc $a^r\equiv{1} [11]$ mais r est inférieur à i et comme i est le plus petit entier non nul vérifiant $a^i\equiv{1} [11]$ alors $r=0$ ainsi i est un diviseur de 10 : $i \in{\{1;2;5;10}\}$
3d. D’après 3a. a doit vérifier pour tout $i<10$, $a^i \not\equiv{1} [11]$. On effectue cette vérification pour $i=1$, $i=2$ et $i=5$
- pour a=1, on a $1^1 = 1 [11]$, donc 1 n’est pas solution
- pour a=2, on a $2^1=1 [11]$, $2^2=4 [11]$, $2^5=10 [11]$, donc 2 est solution
- pour a=3, on a $3^1= 3[11]$, $3^2= 9[11]$, $3^5=1 [11]$, donc 3 n’est pas solution
- pour a=4, on a $4^1= 4[11]$, $4^2= 5[11]$, $4^5=1 [11]$, donc 4 n’est pas solution
- pour a=5, on a $5^1= 5[11]$, $5^2= 3[11]$, $5^5=1 [11]$, donc 5 n’est pas solution
- pour a=6, on a $6^1=6 [11]$, $6^2=3 [11]$, $6^5=10 [11]$, donc 6 est solution
- pour a=7, on a $7^1=7 [11]$, $7^2=5 [11]$, $7^5=10 [11]$, donc 7 est solution
- pour a=8, on a $8^1=8 [11]$, $8^2=9 [11]$, $8^5=10 [11]$, donc 8 est solution
- pour a=9, on a $9^1=9 [11]$, $9^2=4 [11]$, $9^5=1 [11]$, donc 9 n’est pas solution
- pour a=10, on a $10^1=10 [11]$, $10^2=1 [11]$, donc 10 n’est pas solution
En définitive, l’ensemble S des solution est : $S= {\{2;6;7;8}\}$