quelques corrections

[modelisationMathS3.git] / rsa.tex

diff --git a/rsa.tex b/rsa.tex
index 0316be6eb030b94ad06ca71e1594d05a83d82bc7..a96d0a218530f7186b0e729625d0bb8491ec39a1 100644 (file)
--- a/rsa.tex
+++ b/rsa.tex
@@ -305,30 +305,6 @@ d'inconnues $x$ et $y$.
 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

-\begin{Exo}
-On considère l'algorithme suivant: 
-on choisit deux nombres premiers $p$ et $q$
-distincts tels que 
-$p \equiv 2 [3]$ et $s \equiv 2 [3]$.
-Soit $n = pq$. 
-Alice veut envoyer un message  à Bob. 
-Comme dans RSA, son message est un nombre $m \in \ \{1, . . . , n - 1\}$ 
-tel que $m \land  n = 1$
-Le message codé d'Alice est le résultat $a= m^3[n]$.
-Bob décode $a$ en calculant 
-\[
-m' \equiv a^{d} [n] \textrm{ où $d=\dfrac{2(p-1)(q-1)+1}{3}$} 
-\]
-Normalement $m$ doit être égal à $m'$.
-
-\begin{enumerate}
-\item Choisir $p=11$, $q=17$, $m=4$ puis construire le message codé ainsi que le message décodé.
-\item  Montrer que $d$ est toujours un entier.
-\item Expliquer pourquoi $a$ et $m'$ ne sont pas divisibles par $n$.
-\item Montrer que Bob a bien décodé le message d’Alice.
-\end{enumerate}
-
-\end{Exo}

 
 \begin{Exo}[Sujet du bac S Liban 2005]
 On rappelle le résultat suivant appelé le corollaire du 
 
 \begin{Exo}[Sujet du bac S Liban 2005]
 On rappelle le résultat suivant appelé le corollaire du 


@@ -444,9 +420,9 @@ $261x +2$ soit multiple de 305.
 
 \begin{Exo}
 \begin{enumerate}
 
 \begin{Exo}
 \begin{enumerate}

-\item Démonter que $35 \equiv 1 [11]$
+\item Démonter que $3^5 \equiv 1 [11]$

 \item En déduire que pour tous entiers naturels $k$ et $r$ on a 
 \item En déduire que pour tous entiers naturels $k$ et $r$ on a 

-                                        $35k +r \equiv 3r [11]$.
+                                        $3^{5k +r} \equiv 3^r [11]$.

 \item  $n$ étant un entier naturel, quels sont les restes possibles
   dans la division de $3^n$ par 11?
 \item  Trouvez pour quelles valeurs de $n$, $3^n + 7$ est divisible par 11.
 \item  $n$ étant un entier naturel, quels sont les restes possibles
   dans la division de $3^n$ par 11?
 \item  Trouvez pour quelles valeurs de $n$, $3^n + 7$ est divisible par 11.


@@ -492,6 +468,32 @@ a^d & \equiv &   (m^e)^d [n]\\
 \end{Proof}
 
 
 \end{Proof}
 
 

+\begin{Exo}
+On considère l'algorithme suivant: 
+on choisit deux nombres premiers $p$ et $q$
+distincts tels que 
+$p \equiv 2 [3]$ et $s \equiv 2 [3]$.
+Soit $n = pq$. 
+Alice veut envoyer un message  à Bob. 
+Comme dans RSA, son message est un nombre $m \in \ \{1, . . . , n - 1\}$ 
+tel que $m \land  n = 1$
+Le message codé d'Alice est le résultat $a= m^3[n]$.
+Bob décode $a$ en calculant 
+\[
+m' \equiv a^{d} [n] \textrm{ où $d=\dfrac{2(p-1)(q-1)+1}{3}$} 
+\]
+Normalement $m$ doit être égal à $m'$.
+
+\begin{enumerate}
+\item Choisir $p=11$, $q=17$, $m=4$ puis construire le message codé ainsi que le message décodé.
+\item  Montrer que $d$ est toujours un entier.
+\item Expliquer pourquoi $a$ et $m'$ ne sont pas divisibles par $n$.
+\item Montrer que Bob a bien décodé le message d’Alice.
+\end{enumerate}
+
+\end{Exo}
+
+

 \begin{Prop}[Petit théorème de Fermat]
 Si $p$ est un nombre premier et $a$ un entier 
 alors $a^{p} \equiv a [p]$.
 \begin{Prop}[Petit théorème de Fermat]
 Si $p$ est un nombre premier et $a$ un entier 
 alors $a^{p} \equiv a [p]$.


@@ -550,8 +552,11 @@ Calculer $2^{500} [13]$ et $26^{1000} [17]$.
 
 
 \begin{Exo}
 
 
 \begin{Exo}

-Montrer que l'entier naturel $n$ est premier si et seulement si 
-$$(x +1) ^n \equiv x ^n +1[n].$$
+Montrer que si l'entier naturel $n$ est premier alors
+$$(x +1)^n \equiv x^n +1[n].$$
+
+On a même l'équivalence, cependant, l'autre sens est plus technique à démontrer.
+

 \end{Exo}
 
 
 \end{Exo}