Exercice : Clés de contrôle, cryptographie et codes correcteurs

Étape 1

On sait que $y \equiv a x + b \pmod{26}$ avec $b = 3$, $x = 11$ et $y = 8$. En remplaçant ces valeurs dans la congruence, on obtient : $$11 a + 3 \equiv 8 \pmod{26}$$

Étape 2

En soustrayant $3$ aux deux membres de la congruence, on a : $$11 a \equiv 8 - 3 \pmod{26}$$ ce qui donne : $$11 a \equiv 5 \pmod{26}$$

Étape 3

Pour déterminer $a$, on cherche l'inverse de $11$ modulo $26$, c'est-à-dire l'entier $u \in \{0, \dots, 25\}$ tel que $11 u \equiv 1 \pmod{26}$. On applique l'algorithme d'Euclide : $$26 = 2 \times 11 + 4$$ $$11 = 2 \times 4 + 3$$ $$4 = 1 \times 3 + 1$$

Étape 4

En remontant les égalités, on obtient l'identité de Bézout : $$1 = 4 - 1 \times 3$$ $$1 = 4 - (11 - 2 \times 4) = 3 \times 4 - 11$$ $$1 = 3 \times (26 - 2 \times 11) - 11 = 3 \times 26 - 7 \times 11$$

Étape 5

On en déduit que $-7 \times 11 \equiv 1 \pmod{26}$. Comme $-7 \equiv 19 \pmod{26}$ car $-7 + 26 = 19$, l'inverse modulaire de $11$ modulo $26$ est $19$.

Étape 6

En multipliant la congruence $11 a \equiv 5 \pmod{26}$ par $19$, on trouve : $$19 \times 11 a \equiv 19 \times 5 \pmod{26}$$ Comme $19 \times 11 \equiv 1 \pmod{26}$, cela équivaut à : $$a \equiv 95 \pmod{26}$$

Étape 7

Or $95 = 3 \times 26 + 17$, donc $95 \equiv 17 \pmod{26}$. Le coefficient $a$ recherché est donc $17$.