Introduction
Le sujet original peut être trouvé à cette adresse, via l'APMEP.
Modifications effectuées :
- la partie D a été ajoutée.
Partie A : Restitution organisée de connaissance
Soient $a$, $b$, $c$ et $d$ des entiers relatifs et $n$ un entier naturel non nul.
Montrer que si on a :
$$
\left\{
\begin{array}{lcl}
a \equiv b \mod{n} \\
c \equiv d \mod{n}
\end{array}
\right.
$$
alors :
$$
ac \equiv bd \mod{n}
$$
Partie B : Inverse de 23 modulo 26
On considère l’équation :
$$
(E) : 23x −26y = 1
$$
où x et y désignent deux entiers relatifs.
- Vérifier que le couple $(-9, -8)$ est solution de l’équation $(E)$.
- Résoudre alors l’équation $(E)$.
-
En déduire un entier $a$ tel que :
$$
0 \leq a \leq 25
$$
et :
$$
23a \equiv 1 \mod{26}
$$
Partie C : Chiffrement de Hill
On veut coder un mot de deux lettres selon la procédure suivante :
Étape 1
Chaque lettre du mot est remplacée par un entier en utilisant le tableau
ci-dessous :
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
On obtient un couple d’entiers $(x_1 ; x_2)$ où $x_1$ correspond à la première lettre
du mot et $x_2$ correspond à la deuxième lettre du mot.
Étape 2
$(x_1 ; x_2)$ est transformé en $(y_1 ; y_2)$ tel que
$$
S_1 =
\left\{
\begin{array}{lcl}
y_1 & \equiv & 11x_1 + 3x_2 \mod{26} \\
y_2 & \equiv & 7x_1 + 4x_2 \mod{26}
\end{array}
\right.
\mbox{ avec }
0 \leq y_1 \leq 25
\mbox{ et }
0 \leq y_2 \leq 25
$$
Étape 3
$(y_1 ; y_2)$ est transformé en un mot de deux lettres en utilisant le tableau
de correspondance donné dans l'étape 1.
Exemple :
$$
\underbrace{TE}_{\mbox{mot en clair}}
\overbrace{\Longrightarrow}^{\mbox{Étape 1}}
(19,4)
\overbrace{\Longrightarrow}^{\mbox{Étape 2}}
(13,19)
\overbrace{\Longrightarrow}^{\mbox{Étape 3}}
\underbrace{NT}_{\mbox{mot codé}}
$$
- Coder le mot ST.
- On veut maintenant déterminer la procédure de décodage :
-
Montrer que tout couple $(x_1 ; x_2)$ vérifiant les équations du système
$(S_1)$, vérifie les équations du système :
$$
S_2 =
\left\{
\begin{array}{lcl}
23x_1 & \equiv & 4y_1 + 23y_2 \mod{26} \\
23x_2 & \equiv & 19y_1 + 11y_2 \mod{26}
\end{array}
\right.
$$
-
À l’aide de la partie B, montrer que tout couple $(x_1 ; x_2)$ vérifiant les
équations du système $(S_2)$, vérifie les équations du système :
$$
S_3 =
\left\{
\begin{array}{lcl}
x_1 & \equiv & 16y_1 + y_2 \mod{26} \\
x_2 & \equiv & 11y_1 + 5y_2 \mod{26}
\end{array}
\right.
$$
-
Montrer que tout couple $(x_1 ; x_2)$ vérifiant les équations du système
$(S_3)$, vérifie les équations du système $(S_1)$.
- Décoder le mot YJ.
Partie D : Programmation
Non demandé au BAC
- Programmer un algorithme convertissant une lettre en un nombre, et un nombre en une lettre.
Aller faire évaluer votre algorithme
- Programmer un algorithme permettant d'encoder un mot de deux caractères, en utilisant la procédure de la partie C.
Aller faire évaluer votre algorithme
- Montrer qu'il suffit,dans l'algorithme, de remplacer les coefficients (11,3,7,4) par (16,1,11,5) pour pouvoir décoder un mot de deux caractères.
- Programmer un algorithme permettant de d'encoder / décoder un texte complet de longueur paire avec des coefficients donnés.
Aller faire évaluer votre algorithme