\textbf{Part A - Hill Cipher}

Here are the different encryption steps for a word with an even number of letters:

\begin{center}
\begin{tabular}{|l|l|}
\hline
Step 1 & The word is divided into blocks of two consecutive letters, then for each block, each of the following steps is performed. \\
\hline
Step 2 & To the two letters of the block are associated two integers $x_1$ and $x_2$ both between 0 and 25, which correspond to the two letters in the same order, in the following table:
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F & G & H & I & J & K & L & M \\
\hline
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\
\hline\hline
N & O & P & Q & R & S & T & U & V & W & X & Y & Z \\
\hline
13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\
\hline
\end{tabular} \\
\hline
Step 3 & The matrix $X = \binom{x_1}{x_2}$ is transformed into the matrix $Y = \binom{y_1}{y_2}$ satisfying $Y = AX$, where $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$. \\
\hline
Step 4 & The matrix $Y = \binom{y_1}{y_2}$ is transformed into the matrix $R = \binom{r_1}{r_2}$, where $r_1$ is the remainder of the Euclidean division of $y_1$ by 26 and $r_2$ is the remainder of the Euclidean division of $y_2$ by 26. \\
\hline
Step 5 & To the integers $r_1$ and $r_2$ are associated the two corresponding letters from the table in step 2. The encrypted block is the block obtained by concatenating these two letters. \\
\hline
\end{tabular}
\end{center}

Use the encryption method presented to encrypt the word ``HILL''.

\textbf{Part B - Some mathematical tools necessary for decryption}

\begin{enumerate}
  \item Let $a$ be an integer relatively prime to 26. Prove that there exists an integer $u$ such that $u \times a \equiv 1$ modulo 26.
  
  \item Consider the following algorithm:
  \begin{center}
  \begin{tabular}{|l|l|}
  \hline
  VARIABLES : PROCESSING : & \begin{tabular}{l}
  $a, u$, and $r$ are numbers ($a$ is a natural number and relatively prime to 26) \\
  Read $a$ \\
  $u$ takes the value 0, and $r$ takes the value 0 \\
  While $r \neq 1$ \\
  $u$ takes the value $u + 1$ \\
  $r$ takes the value of the remainder of the Euclidean division of $u \times a$ by 26 \\
  End While \\
  Display $u$ \\
  \end{tabular} \\
  \hline
  \end{tabular}
  \end{center}
  The value $a = 21$ is entered into this algorithm.\\
  a. Reproduce on your paper and complete the following table, until the algorithm stops.
  \begin{center}
  \begin{tabular}{|c|c|c|c|l}
  \hline
  $u$ & 0 & 1 & 2 & $\ldots$ \\
  \hline
  $r$ & 0 & 21 & $\ldots$ & $\ldots$ \\
  \hline
  \end{tabular}
  \end{center}
  b. Deduce that $5 \times 21 \equiv 1$ modulo 26.
  
  \item Recall that $A$ is the matrix $A = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right)$ and denote by $I$ the matrix: $I = \left(\begin{array}{ll} 1 & 0 \\ 0 & 1 \end{array}\right)$.\\
  a. Calculate the matrix $12A - A^2$.\\
  b. Deduce the matrix $B$ such that $BA = 21I$.\\
  c. Prove that if $AX = Y$, then $21X = BY$.
\end{enumerate}

\textbf{Part C - Decryption}

We want to decrypt the word VLUP. We denote by $X = \binom{x_1}{x_2}$ the matrix associated, according to the correspondence table, to a block of two letters before encryption, and $Y = \binom{y_1}{y_2}$ the matrix defined by the equality: $Y = AX = \left(\begin{array}{ll} 5 & 2 \\ 7 & 7 \end{array}\right) X$. If $r_1$ and $r_2$ are the respective remainders of $y_1$ and $y_2$ in the Euclidean division by 26, the block of two letters after encryption is associated with the matrix $R = \binom{r_1}{r_2}$.

\begin{enumerate}
  \item Prove that: $\left\{ \begin{aligned} 21x_1 &= 7y_1 - 2y_2 \\ 21x_2 &= -7y_1 + 5y_2 \end{aligned} \right.$
  
  \item Using question B.2., establish that: $\begin{cases} x_1 \equiv 9r_1 + 16r_2 & \text{modulo } 26 \\ x_2 \equiv 17r_1 + 25r_2 & \text{modulo } 26 \end{cases}$
  
  \item Decrypt the word VLUP, associated with the matrices $\binom{21}{11}$ and $\binom{20}{15}$.
\end{enumerate}