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.

1. Vérifier que le couple $(-9, -8)$ est solution de l’équation $(E)$.
2. Résoudre alors l’équation $(E)$.
3. 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é}} $$

1. Coder le mot ST.
2. On veut maintenant déterminer la procédure de décodage :
   1. 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. $$
   2. À 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. $$
   3. 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)$.
   4. Décoder le mot YJ.

Partie D : Programmation

Non demandé au BAC

1. Programmer un algorithme convertissant une lettre en un nombre, et un nombre en une lettre.
   Aller faire évaluer votre algorithme
2. 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
3. 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.
4. 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