On considère les matrices $A= \frac12\begin{pmatrix} 0&1&1 \\ 1&0&1\\ 1&1&0 \end{pmatrix}$ et $P= \begin{pmatrix} 1&-1&-1 \\ 1&1&0\\ 1&0&1 \end{pmatrix}$.

1. En résolvant le système $PX=Y$ avec $X= \begin{pmatrix} x \\ y\\ z \end{pmatrix}$ et $Y= \begin{pmatrix} a \\ b\\ c \end{pmatrix}$.

   Montrer que $P$ est inversible et donner son inverse.

2. Calculer $P^{-1}AP$.
3. Déterminer $A^n$ pour tout entier naturel $n$.

4. On considère les trois suites $(u_n)$, $(v_n)$ et $(w_n)$ définies par récurrence, pour $u_0$, $v_0$ et $w_0$ des réels , par :

   $ \left \{ \begin{array}{c c} u_{n+1} & =\frac{v_n+w_n}{2} \\ v_{n+1} &=\frac{u_n+w_n}{2}\\w_{n+1}&=\frac{u_n+v_n}{2} \\ \end{array} \right. ,n\in\mathbb{N}$. On pose $U_n=\begin{pmatrix}u_n\\v_n\\w_n\end{pmatrix}$, pour tout $n\in\mathbb{N}$.

   1. Déterminer une relation matricielle entre $U_{n+1}$ et $U_{n}$ pour tout entier $n$.

   2. En déduire les limites des trois suites.

Le but de cet exercice est d'étudier, sur un exemple, une méthode de chiffrement publiée en 1929 par le mathématicien et cryptologue Lester Hill.
Ce chiffrement repose sur la donnée d'une matrice $A$, connue uniquement de l'émetteur et du destinataire.

Dans les parties 1 et 3 de cet exercice, cette matrice de cryptage est notée $A$ et est définie par : $A = \begin{pmatrix}11&8\\6&5\end{pmatrix}$.
Attention ! La dernière partie est indépendante et nécessitera que vous mettiez en commun vos réflexions et calculs.

Partie A : cryptage

Voici les différentes étapes de chiffrement pour un mot comportant un nombre pair de lettres :

1. On divise le mot en blocs de deux lettres consécutives puis, pour chaque bloc, on effectue chacune des étapes suivantes.

2. On associe aux deux lettres du bloc les deux entiers $x_1$ et $x_2$ tous deux compris entre 0 et 25, qui correspondent aux deux lettres dans le même ordre, dans le tableau suivant :

   A	B	C	D	E	F	G	H	I	J	K	L	M
   0	1	2	3	4	5	6	7	8	9	10	11	12

   N	O	P	Q	R	S	T	U	V	W	X	Y	Z
   13	14	15	16	17	18	19	20	21	22	23	24	25

3. On transforme la matrice $X = \begin{pmatrix}x_1\\x_2\end{pmatrix}$ en la matrice $Y = \begin{pmatrix}y_1\\y_2\end{pmatrix}$ vérifiant $Y = A X$.

4. On transforme la matrice $Y = \begin{pmatrix}y_1\\y_2\end{pmatrix}$ en la matrice $R = \begin{pmatrix}r_1\\r_2\end{pmatrix}$, où $r_1$ est le reste de la division euclidienne de $y_1$ par 26 et $r_2$ celui de la division euclidienne de $y_2$ par 26.

5. On associe aux entiers $r_1$ et $r_2$ les deux lettres correspondantes du tableau de l'étape 2.

   Le bloc chiffré est le bloc obtenu en juxtaposant ces deux lettres.

1. utiliser la méthode de chiffrement exposée pour chiffrer le mot HILL.

Partie B : un programme informatique utile pour une étape du décryptage

On considère la fonction suivante écrite en langage naturel :

                fonction(a un nombre entier naturel) :
    n prend la valeur 0
    r prend la valeur 0
    Tant que r≠1 et n<26 :
        n est incrémenté de 1
        r prend la valeur du reste de la division euclidienne de n×a par 26
    Fin Tant que 
    renvoyer n
                

2. 1. La fonction prend comme argument la valeur $a = 7$.

      Reproduire et compléter le tableau suivant jusqu'à l'arrêt de l'algorithme. Vous devez saisir dans ce tableau les valeurs successivement prises par les variables n et r au cours de l'exécution de l'algorithme.

      n	0	1	2	...
      r	0	...	...	...

   2. En déduire l'existence d'un nombre entier naturel $k$ tel que $7\times k \equiv 1\ [26]$.

   3. Écrire la fonction précédente en langage Python puis vérifier le résultat obtenu précédemment.

   4. Que renvoie la fonction précédente codée en Python lorsque son argument est 8 ?
      Expliquer la signification de la valeur obtenue.

   5. Écrire une fonction liste_resultats qui ne prend pas de paramètre d'entrée et qui renvoie la liste des 26 résulats retourné par la fonction précédente ; le terme d'index $i$ correspond donc au renvoi de la fonction précédente lorsqu'en entrée son argument est $i$.

   6. Conjecturer une condition nécessaire et suffisante portant sur un entier naturel $i$ compris entre 0 et 25 pour que le renvoi de la fonction précédente ne soit pas 26.

Partie C : décryptage d'un message codé

3. 1. Justifier que la matrice $A$ la matrice définie par : $\begin{pmatrix}11&8\\6&5\end{pmatrix}$ admet une matrice inverse dans $\mathcal{M}_{np}(\mathbb{R})$, matrice à déterminer.

   2. Pour pouvoir décrypter des messages codés à partir de la matrice $A$, il faut obtenir une matrice $B$ a coefficients entiers telle que $AB=BA=\begin{pmatrix}i_{11}&i_{12}\\i_{21}&i_{22}\end{pmatrix}$ où $i_{11}\equiv 1\ [26]$, $i_{12}\equiv 0\ [26]$, $i_{21}\equiv 0\ [26]$ et $i_{22}\equiv 1\ [26]$.
      Pourquoi la matrice obtenue à la question précédente ne convient pas ?

4. On rappelle que $A$ est la matrice $A = \begin{pmatrix}11&8\\6&5\end{pmatrix}$ et on note $I$ la matrice : $I = \begin{pmatrix}1&0\\0&1\end{pmatrix}$.

   1. Calculer la matrice $16A-A^2$.

   2. En déduire la matrice $B$ telle que $BA = 7I$.

   3. Démontrer que si $A X = Y$, alors $7 X = B Y$

5. On veut déchiffrer le mot XUSL.

   On note $X = \begin{pmatrix}x_1\\x_2\end{pmatrix}$ la matrice associée, selon le tableau de correspondance, à un bloc de deux lettres avant chiffrement, et $Y = \begin{pmatrix}y_1\\y_2\end{pmatrix}$ la matrice définie par l'égalité : $Y = A X = \begin{pmatrix}11&8\\6&5\end{pmatrix}X$.

   Si $r_1$ et $r_2$ sont les restes respectifs de $y_1$ et $y_2$ dans la division euclidienne par 26, le bloc de deux lettres après chiffrement est associé à la matrice $R = \begin{pmatrix}r_1\\r_2\end{pmatrix}$.

   1. Démontrer que : $\left\{\begin{array}{l c l} 7x_1 &=& \phantom{-}5y_1 - 8y_2\\ 7x_2 &=&- 6y_1 + 11 y_2 \end{array}\right.$.

   2. En utilisant des questions précédentes, établir que : $\left\{\begin{array}{l c l r} x_1 &\equiv&23r_1 + 10r_2 \:\:&[26]\\ x_2 &\equiv&14r_1 + 9r_2 \:\:&[26] \end{array}\right.$.

   3. Décrypter le mot XUSL, associé aux matrices $\begin{pmatrix}23\\20\end{pmatrix}$ et $\begin{pmatrix}18\\11\end{pmatrix}$.

Partie D : nouvelle mission secrète pour vous

Les services secrets français de contre-espionnage pour qui vous travaillez en secret viennent de vous confier une nouvelle mission : décrypter le message envoyé par le groupe que vous surveillez. Voici le message crypyté reçu :