Exercice 13 Inverse modulaire et chiffrement affine

1. Algorithme d'Euclide : $$\begin{aligned} 26 &= 11\times 2+4 \qquad (L_{1}) \\ 11 &= 4\times 2+3 \qquad (L_{2}) \\ 4 &= 3\times 1+1 \qquad (L_{3}) \end{aligned}$$ Remontée : $$\begin{aligned} 1 &= 4-\textcolor{#9e0018}{3} &&\text{or } (L_{2}) : \; 3=11-4\times 2 \\ &= 4-\textcolor{#9e0018}{(11-4\times 2)}=3\times\textcolor{#9e0018}{4}-11 &&\text{or } (L_{1}) : \; 4=26-11\times 2 \\ &= 3\times\textcolor{#9e0018}{(26-11\times 2)}-11=3\times 26-7\times 11 && \end{aligned}$$

$$\boxed{(u\,;v)=(-7\,;3) \quad \text{car} \quad 11\times(-7)+26\times 3=-77+78=1}$$ On en déduit $11\times(-7)\equiv 1\;[26]$. Comme $-7\equiv 19\;[26]$ : $$\boxed{x_{0}=19} \qquad \text{vérification : } 11\times 19=209=8\times 26+1$$

2. Si $11x\equiv 5\;[26]$, on multiplie par $19$ : $209x\equiv 95\;[26]$, c'est-à-dire $x\equiv 95\equiv 17\;[26]$, car $209\equiv 1$ et $95=3\times 26+17$. Réciproquement, si $x\equiv 17\;[26]$, alors $11x\equiv 187=7\times 26+5\equiv 5\;[26]$. $$\boxed{S=\left\{17+26k \; ; \; k\in\mathbb{Z}\right\}}$$ Multiplier par l'inverse de $11$ joue le même rôle que diviser par $11$ dans une équation réelle.

3. (a) $E$ a pour rang $4$ : $11\times 4+3=47=26+21$, donc $y=21$, qui est le rang de $V$. $\boxed{E \text{ est codé en } V}$

(b) Si $y\equiv 11x+3\;[26]$, alors $y-3\equiv 11x$, et en multipliant par $19$ : $19(y-3)\equiv 209x\equiv x\;[26]$. Réciproquement, si $x\equiv 19(y-3)$, alors $11x\equiv 209(y-3)\equiv y-3\;[26]$. Pour $H$, de rang $7$ : $$x\equiv 19\times 4=76=2\times 26+24\equiv 24\;[26]$$

$$\boxed{H \text{ se décode en } Y}$$ On vérifie : $11\times 24+3=267=10\times 26+7$, qui est bien le rang de $H$.

(c) $13$ et $26$ ne sont pas premiers entre eux : $13$ n'a pas d'inverse modulo $26$. Concrètement, $13x$ est congru à $0$ ou à $13$ modulo $26$ selon la parité de $x$, donc $13x+3$ ne prend que les valeurs $3$ et $16$ modulo $26$. Par exemple, $A$ et $C$ sont tous deux codés en $D$ : le décodage est impossible.