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.
  2. $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$.
  3. Déterminer le nombre qui code la lettre «O ».
  4. $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]$.
  2. 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$
    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é.
    2. 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$
    3. 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]$.
    4. 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$
    5. 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.$
    6. 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*}$
    1. Déterminer les nombres entiers naturels $a$ tels que $0 \leqslant a < 3$ et $a^2 \equiv 1 \:\: [3]$.
    2. $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$.
    3. Déterminer les nombres entiers naturels $b$ tels que $0 \leqslant b < 11$ et $b^2 \equiv 4\:\: [11]$.
    4. $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$
    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.\]
    2. 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$
    3. 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.
    4. 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$.
  3. Compléter l'algorithme en Annexe pour qu'il affiche les quatre solutions trouvées dans la question précédente.

  4. 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$
  5. 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 ?
  6. 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.
Page
  • Vues: 15314

Rechercher