Baccalauréat S Pondichéry 4 mai 2018 - Correction Spécialité

Page 10 sur 10: Correction Spécialité

Correction de l'exercice de Spécialité 5 points

Candidats AYANT SUIVI l'enseignement de spécialité mathématiques

À toute lettre de l'alphabet on associe un nombre entier $x$ compris entre 0 et 25 comme indiqué dans le tableau ci-dessous: $$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \text{Lettre } &A &B &C &D &E &F &G &H &I &J &K &L &M\\ \hline x &0 &1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12\\ \hline\hline \text{Lettre } &N &O &P &Q &R &S &T &U &V &W &X &Y &Z\\ \hline x &13&14&15&16&17&18&19&20&21&22&23 &24 &25\\ \hline \end{array}$$
Le «chiffre de RABIN » est un dispositif de cryptage asymétrique inventé en 1979 par l'informaticien Michael Rabin.
Alice veut communiquer de manière sécurisée en utilisant ce cryptosystème. Elle choisit deux nombres premiers distincts $p$ et $q$. Ce couple de nombres est sa clé privée qu'elle garde secrète. Elle calcule ensuite $n = p \times q$ et elle choisit un nombre entier naturel $B$ tel que $0 \leqslant B \leqslant n -1$. Si Bob veut envoyer un message secret à Alice, il le code lettre par lettre. Le codage d'une lettre représentée par le nombre entier $x$ est le nombre $y$ tel que : \[y \equiv x(x + B)\:\: [n] \:\text{ avec }\: 0 \leqslant y \leqslant n.\] Dans tout l'exercice on prend $p = 3,\: q = 11$ donc $n = p \times q = 33$ et $B = 13$.

Partie A : Cryptage

Bob veut envoyer le mot « NO » à Alice.

1. Montrer que Bob code la lettre «N » avec le nombre 8.
$N$ est associé au nombre $x=13$.
Ainsi $y \equiv 13(13+13) ~~[33] \equiv 338~~[33]\equiv 8~~[33]$.
Donc Bob code la lettre $N$ avec le nombre $8$.

2. Déterminer le nombre qui code la lettre «O ».
$O$ est associé au nombre $x=14$.
Ainsi $y \equiv 14(14+13) ~~[33] \equiv 378~~[33]\equiv 15~~[33]$.
Donc Bob code la lettre $O$ avec le nombre $15$.
$\quad$

 

Partie B : Décryptage

Alice a reçu un message crypté qui commence par le nombre 3. Pour décoder ce premier nombre, elle doit déterminer le nombre entier $x$ tel que : \[x(x + 13) \equiv 3 \:\: [33]\: \text{ avec }\: 0 \leqslant x < 26.\]

1. Montrer que $x(x + 13) \equiv 3\:\: [33]$ équivaut à $(x + 23)^2 \equiv 4\:\: [33]$.
On a :
$\begin{align*} (x+23)^2\equiv 4~~[33] &\iff x^2+46x+529 \equiv 4 ~~[33] \\
&\iff x^2+46x\equiv -525~~[33] \\
&\iff x^2+13x\equiv 3~~[33] \\
&\iff x(x+13)\equiv 3~~[33]\\
\end{align*}$
$\quad$
2. 1. Montrer que si $(x + 23)^2 \equiv 4\:\: [33]$ alors le système d'équations $\left\{\begin{array}{l c l} (x + 23)^2 &\equiv &4 \:\: [3]\\ (x + 23)^2 &\equiv &4 \:\: [11] \end{array}\right.$ est vérifié.
   Si $(x+23)^2\equiv 4~~[33]$ alors il existe un entier relatif $k$ tel que : $(x+23)^2=4+33k $
   Or $(x+23)^2=4+33k \iff (x+23)^2=4+11k\times 3$
   Donc $(x+23)^2\equiv 4~~[3]$
   De plus $(x+23)^2=4+33k \iff (x+23)^2=4+3k\times 11$
   Donc $(x+23)^2\equiv 4~~[11]$
   Par conséquent le système $\begin{cases} (x+23)^2\equiv 4~~[3]\\(x+23)^2\equiv 4~~[11]\end{cases}$ est vérifié.
   $\quad$
   
   2. Réciproquement, montrer que si $\left\{\begin{array}{l c l} (x + 23)^2 &\equiv &4\:\: [3]\\ (x + 23)^2 &\equiv &4 \:\: [11] \end{array}\right.$ alors $(x + 23)^2 \equiv 4\:\: [33]$.
   Si le système $\begin{cases} (x+23)^2\equiv 4~~[3]\\(x+23)^2\equiv 4~~[11]\end{cases}$ est vérifié alors il existe deux entiers relatifs $k$ et $k’$ tels que
   $(x+23)^2=4+3k$ et $(x+23)^2=4+11k’$.
   Par conséquent $4+3k=4+11k’ \iff 3k=11k’$.
   Les nombres $3$ et $11$ sont premiers entre-eux.
   D’après le théorème de Gauss cela signifie donc que $3$ divise $k’$.
   Par conséquent, il existe un entier relatif $q$ tel que $k’=3q$.
   Ainsi $(x+23)^2=4+11\times 3q=4+33q$.
   Donc $(x+23)^2\equiv 4~~[33]$.
   $\quad$
   
   3. En déduire que $x(x + 13) \equiv 3\:\: [33] \iff \left\{\begin{array}{l c l} (x + 23)^2 &\equiv&1 \:\: [3]\\ (x + 23)^2 &\equiv& 4 \:\: [11] \end{array}\right.$
   On a donc :
   $\begin{align*} x(x+13)\equiv 3~~[33]&\iff (x+23)^2\equiv 4~~[33] \\
   &\iff \begin{cases} (x+23)^2\equiv 4~~[3]\\(x+23)^2\equiv 4~~[11]\end{cases}
   &\iff \begin{cases} (x+23)^2\equiv 1~~[3]\\(x+23)^2\equiv 4~~[11]\end{cases}
   \end{align*}$
3. 1. Déterminer les nombres entiers naturels $a$ tels que $0 \leqslant a < 3$ et $a^2 \equiv 1 \:\: [3]$.
   $0^2=0 \equiv 0~~[3]$
   $1^1=1\equiv 1~~[3]$
   $2^2=4\equiv 1~~[3]$
   Donc les entiers naturels vérifiant $0\leq a<3$ et $a^2\equiv 1~~[3]$ sont $1$ et $2$.
   
   2. Déterminer les nombres entiers naturels $b$ tels que $0 \leqslant b < 11$ et $b^2 \equiv 4\:\: [11]$.
   $0^2=0\equiv 0~~[11]$
   $1^2=1\equiv 1~~[11]$
   $2^2=4\equiv 4~~[11]$
   $3^2=8\equiv 9~~[11]$
   $4^2=16\equiv 5~~[11]$
   $5^2=25\equiv 3~~[11]$
   $6^2=36\equiv 3~~[11]$
   $7^2=49\equiv 5~~[11]$
   $8^2=64\equiv 9~~[11]$
   $9^2=81\equiv 4~~[11]$
   $10^2=100\equiv 1~~[11]$
   Donc les entiers naturels vérifiant $0\leq b<11$ et $b^2\equiv 4~~[11]$ sont $2$ et $9$.
   $\quad$
4. 1. En déduire que $x(x + 13) \equiv 3 \quad[33]$ équivaut aux quatre systèmes suivants : \[\left\{\begin{array}{l c l} x &\equiv&2\quad [3]\\ x&\equiv &8\quad[11] \end{array}\right. \: \text{ ou } \left\{\begin{array}{l c l} x &\equiv& 0\quad[3]\\ x &\equiv& 1 \quad[11] \end{array}\right.\: \text{ ou } \left\{\begin{array}{l c l} x &\equiv& 2\quad[3]\\ x &\equiv&1 \quad[11] \end{array}\right.\: \text{ ou } \left\{\begin{array}{l c l} x &\equiv& 0\quad [3]\\ x &\equiv& 8 \quad [11] \end{array}\right.\]
   Ainsi $x(x+13)\equiv 3~~[33]$ équivaut à
   $\begin{cases} x+23\equiv 1~~[3]\\x+23\equiv 2~~[11]\end{cases}$ ou $\begin{cases} x+23\equiv 2~~[3]\\x+23\equiv 2~~[11]\end{cases}$ ou $\begin{cases} x+23\equiv 1~~[3]\\x+23\equiv 9~~[11]\end{cases}$ ou $\begin{cases} x+23\equiv 2~~[3]\\x+23\equiv 9~~[11]\end{cases}$
   Ce qui équivaut à
   $\begin{cases} x\equiv -22~~[3]\\x\equiv -21~~[11]\end{cases}$ ou $\begin{cases} x\equiv -21~~[3]\\x\equiv -21~~[11]\end{cases}$ ou $\begin{cases} x\equiv -22~~[3]\\x\equiv -14~~[11]\end{cases}$ ou $\begin{cases} x\equiv -21~~[3]\\x\equiv -14~~[11]\end{cases}$
   Ce qui équivaut à
   $\begin{cases} x\equiv 2~~[3]\\x\equiv 1~~[11]\end{cases}$ ou $\begin{cases} x\equiv 0~~[3]\\x\equiv 1~~[11]\end{cases}$ ou $\begin{cases} x\equiv 2~~[3]\\x\equiv 8~~[11]\end{cases}$ ou $\begin{cases} x\equiv 0~~[3]\\x\equiv 8~~[11]\end{cases}$
   $\quad$
   
   2. On admet que chacun de ces systèmes admet une unique solution entière $x$ telle que $0 \leqslant x < 33$. Déterminer, sans justification, chacune de ces solutions.
   Si $0\leq x <33$
   Alors :
   – une solution de $\begin{cases} x\equiv 2~~[3]\\x\equiv 8~~[11]\end{cases}$ est $8$.
   – une solution de $\begin{cases} x\equiv 0~~[3]\\x\equiv 1~~[11]\end{cases}$ est $12$.
   – une solution de $\begin{cases} x\equiv 2~~[3]\\x\equiv 1~~[11]\end{cases}$ est $23$.
   – une solution de $\begin{cases} x\equiv 0~~[3]\\x\equiv 8~~[11]\end{cases}$ est $30$.
5. Compléter l'algorithme en Annexe pour qu'il affiche les quatre solutions trouvées dans la question précédente.

Annexe On obtient l’algorithme suivant :
Pour $x$ allant de $0$ à $32$
$\quad$ Si le reste de la division de $x(x+13)$ par $33$ est égal à $3$ alors
$\qquad$ Afficher $x$
$\quad$ Fin Si
Fin Pour
$\quad$
6. Alice peut-elle connaître la première lettre du message envoyé par Bob ? Le «chiffre de RABIN » est-il utilisable pour décoder un message lettre par lettre ?
Pour le nombre $3$ possède il existe $4$ valeurs de $x$ possibles.
Le “chiffre de RABIN” n’est donc pas utilisable pour décoder un message lettre par lettre.