Compétence · Terminale TE.CONG.AFFI.01 Niveau : Moyen

Résoudre une équation de congruence par balayage et utiliser un chiffrement affine

Résoudre f(x) ≡ 0 [n] en examinant les n restes possibles ; inverse d'un entier modulo n ; chiffrement de César et chiffrement affine y ≡ ax + b [26] : chiffrer, puis déchiffrer avec l'inverse de a.

Chapitre : Divisibilité et congruences Filière : Term Maths Expertes Temps de maîtrise : ~45 min

Le cours

Équations de congruence et chiffrement affine~3 min

Méthode — résoudre $f(x)\equiv0\ [n]$ par balayage

Les solutions ne dépendent que du reste de $x$ modulo $n$ : on teste $x\in\{0,\dots,n-1\}$ dans un tableau, et l'ensemble des solutions entières est la réunion des classes $x\equiv r\ [n]$ trouvées (c.-à-d. $x=r+kn$, $k\in\mathbb{Z}$).

Exemple

$3x\equiv2\ [7]$ :

$x$$0$$1$$2$$3$$4$$5$$6$
$3x\ [7]$$0$$3$$6$$2$$5$$1$$4$

seule solution $x\equiv3\ [7]$, c.-à-d. $x=3+7k$, $k\in\mathbb{Z}$.

Exemple

$x^2\equiv1\ [8]$ : $x^2\ [8]$ vaut $0,1,4,1,0,1,4,1$ pour $x=0,\dots,7$ : les solutions sont $x\equiv1,3,5,7\ [8]$, c.-à-d. tous les entiers impairs.

Définition — inverse modulo $n$

$a$ est inversible modulo $n$ s'il existe $u\in\mathbb{Z}$ tel que $au\equiv1\ [n]$ ; $u$ est un inverse de $a$ modulo $n$. On peut alors « simplifier par $a$ » : $ax\equiv b\ [n]\iff x\equiv ub\ [n]$ (multiplier par $u$ dans un sens, par $a$ dans l'autre).
Lecture dans le tableau ci-dessus : $3\times5\equiv1\ [7]$, donc $5$ est l'inverse de $3$ modulo $7$, et $3x\equiv2\iff x\equiv5\times2=10\equiv3\ [7]$. Tous les entiers ne sont pas inversibles : $4x\ [8]$ ne prend que les valeurs $0$ et $4$. Critère général ($a$ et $n$ premiers entre eux) et calcul par l'algorithme d'Euclide étendu : chapitre suivant.

Méthode — chiffrement affine $y\equiv ax+b\ [26]$

Lettres codées $A=0,\dots,Z=25$. Chiffrer : $y$ = reste de $ax+b$ modulo $26$. Déchiffrer : il faut un inverse $u$ de $a$ modulo $26$ (tableau des $au\ [26]$) ; alors $x\equiv u(y-b)\ [26]$. Le chiffre de César est le cas $a=1$.

Exemple

$y\equiv5x+8\ [26]$. Lettre M ($x=12$) : $5\times12+8=68=2\times26+16$, donc $y=16$ : Q.
Inverse de $5$ modulo $26$ : $5\times21=105=4\times26+1\equiv1$, donc $u=21$. Déchiffrer Q : $x\equiv21\times(16-8)=168=6\times26+12\equiv12$ : M ✓.

Conçu et validé par Laurent Jacquet, professeur de mathématiques. Qui conçoit les cours ?

Entraîne-toi sur ce cours

Avec un compte gratuit : les QCM et ta Konfiance après chaque question, et le sentier complet d'un chapitre au choix, rappels et épreuve compris.

S'inscrire gratuitement

Déjà inscrit ? Se connecter

Pour aller plus loin

Maîtrise cette compétence avec Konfia

Tous les sentiers, tous les corrigés détaillés et les rappels de révision : 29 € l'année, ou 4,99 € par mois.

Voir l'abonnement