Étape 1
Pour justifier l'existence de la clé de déchiffrement $d$, déterminons le plus grand commun diviseur de $27$ et $160$ au moyen de l'algorithme d'Euclide :
Étape 2
$$160 = 5 \times 27 + 25$$ $$27 = 1 \times 25 + 2$$ $$25 = 12 \times 2 + 1$$ $$2 = 2 \times 1 + 0$$
Étape 3
Le dernier reste non nul étant $1$, on a $\text{PGCD}(27, 160) = 1$. Les entiers $27$ et $160$ sont premiers entre eux, ce qui garantit l'existence d'un couple d'entiers $(d, k)$ vérifiant l'égalité $27d - 160k = 1$.
Étape 4
Déterminons une solution particulière par la remontée des divisions euclidiennes :
Étape 5
$$1 = 25 - 12 \times 2$$
Étape 6
En isolant $2 = 27 - 1 \times 25$ dans la deuxième ligne :
Étape 7
$$1 = 25 - 12 \times (27 - 25) = 13 \times 25 - 12 \times 27$$
Étape 8
En isolant $25 = 160 - 5 \times 27$ dans la première ligne :
Étape 9
$$1 = 13 \times (160 - 5 \times 27) - 12 \times 27 = 13 \times 160 - 77 \times 27$$
Étape 10
En réordonnant sous la forme $27d - 160k = 1$, on obtient :
Étape 11
$$27 \times (-77) - 160 \times (-13) = 1$$
Étape 12
Le couple $(-77 ; -13)$ est donc une solution particulière.
Étape 13
L'ensemble des solutions entières de l'équation est donné par :
Étape 14
$$d = -77 + 160m \quad \text{et} \quad k = -13 + 27m \quad (m \in \mathbb{Z})$$
Étape 15
Pour obtenir le plus petit exposant $d$ strictement positif, on cherche le plus petit entier $m$ tel que $-77 + 160m > 0$, soit $160m > 77$, ce qui donne $m = 1$.
Étape 16
On calcule alors les valeurs correspondantes :
Étape 17
$$d = -77 + 160 \times 1 = 83$$ $$k = -13 + 27 \times 1 = 14$$
Étape 18
La valeur de l'entier pivot $k$ associé au plus petit exposant de déchiffrement $d > 0$ est égale à $14$.
Méthode clé
Appliquer l'algorithme d'Euclide pour prouver que les nombres sont premiers entre eux, puis le remonter pour résoudre l'équation diophantienne $ax + by = 1$.
Piège à éviter
Confondre l'exposant de déchiffrement $d$ et le facteur multiplicatif $k$, ou oublier de choisir la valeur minimale strictement positive pour $d$.
