quelques corrections

[modelisationMathS3.git] / rsa.tex

diff --git a/rsa.tex b/rsa.tex
index 7301393245b4f6db9167b3f03d93acbcba967a68..a96d0a218530f7186b0e729625d0bb8491ec39a1 100644 (file)
--- a/rsa.tex
+++ b/rsa.tex
@@ -205,11 +205,11 @@ On sait que $a\land b$ est $r_n$ le dernier reste non nul.
 On remonte les équations une à une en démarrant de (\ref{eq:def:rnm2}).
 \begin{eqnarray}
 r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \nonumber \\
 On remonte les équations une à une en démarrant de (\ref{eq:def:rnm2}).
 \begin{eqnarray}
 r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \nonumber \\

-  & = & r_{n-2} - (r_{n-3} - r_{n-2} \times q_{n-1}) \times q_{n} (\textrm{on remplace $r_{n-1}$ par sa def dans (\ref{eq:def:rnm3})}) \nonumber\\
-  & = & r_{n-2}. (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n} (\textrm{factorisation})\nonumber \\
-   & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}(\textrm{on remplace $r_{n-2}$ par sa def dans (\ref{eq:def:rnm4})}) \nonumber \\
+  & = & r_{n-2} - (r_{n-3} - r_{n-2} \times q_{n-1}) \times q_{n} \textrm{ (on remplace $r_{n-1}$ par son expression tirée de  (\ref{eq:def:rnm3})}) \nonumber\\
+  & = & r_{n-2}. (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n} \textrm{ (factorisation)}\nonumber \\
+   & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}\textrm{ (on remplace $r_{n-2}$ par son expression tirée de (\ref{eq:def:rnm4})}) \nonumber \\

 & \vdots & \nonumber \\
 & \vdots & \nonumber \\

-& = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\ 
+& = & \ldots \textrm{ (on remplace $r_{1}$ par son expression tirée de (\ref{eq:def:r1})}) \nonumber\\ 

 & = &ax + by \nonumber
 \end{eqnarray}
 \end{Proof}
 & = &ax + by \nonumber
 \end{eqnarray}
 \end{Proof}


@@ -257,10 +257,10 @@ Si $p$ et $q$ sont deux nombres premiers distincts alors l'égalité
 suivante permet de trouver le valeur de la fonction d'Euler en un seul 
 produit:
 \begin{equation}
 suivante permet de trouver le valeur de la fonction d'Euler en un seul 
 produit:
 \begin{equation}

-\varphi(pq)=(p-1)(q-1) \label{FEuler}
+\varphi(pq)=(p-1)(q-1). \label{FEuler}

 \end{equation} 
 \end{equation} 

-

 \end{Prop}
 \end{Prop}

+

 \begin{Exo}[Preuve de l'expression d'Euler]
 On doit compter le cardinal des nombres de $\{1, 2, . . . , pq -1\}$ qui sont 
 premiers avec $pq$.
 \begin{Exo}[Preuve de l'expression d'Euler]
 On doit compter le cardinal des nombres de $\{1, 2, . . . , pq -1\}$ qui sont 
 premiers avec $pq$.


@@ -278,6 +278,9 @@ premiers avec $pq$.
 
 
 
 
 
 

+
+
+

 %Refaire cet exo avec 27x +8y = 1
 \begin{Exo}
 L'objectif est de résoudre l'équation $(E)$ $405x -120y =15$ 
 %Refaire cet exo avec 27x +8y = 1
 \begin{Exo}
 L'objectif est de résoudre l'équation $(E)$ $405x -120y =15$ 


@@ -294,6 +297,14 @@ d'inconnues $x$ et $y$.
 
 
 
 
 
 

+\begin{Exo}
+  Soit $p$ un nombre premier.
+\begin{enumerate}
+\item Calculer $\varphi(p^2)$.
+\item Est-ce que RSA  fonctionnerait aussi avec l'entier $n = p^2$ à la place de $n=pq$?
+\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 


@@ -334,7 +345,7 @@ $g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
 
 
 
 
 
 

-\section{Arithmétique modulaire}
+\section{Congruence modulo}

 
 \begin{Def}[Congruence modulo]
 Soit $a$ et $b$ deux entiers relatifs.
 
 \begin{Def}[Congruence modulo]
 Soit $a$ et $b$ deux entiers relatifs.


@@ -360,7 +371,7 @@ Démontrer la proposition précédente.
 \end{Exo}
 
 \begin{Prop}
 \end{Exo}
 
 \begin{Prop}

-Soit deux entiers naturels $a$ et $n$ tels que $a< n$.
+Soit deux entiers naturels $a$ et $n$ tels que $1< a< n$.

 Si $a$ et $n$ sont premier entre eux, 
 alors il existe un unique $x \in \{1, \dots, n-1\}$ tel 
 que $ax \equiv 1[n]$.
 Si $a$ et $n$ sont premier entre eux, 
 alors il existe un unique $x \in \{1, \dots, n-1\}$ tel 
 que $ax \equiv 1[n]$.


@@ -370,10 +381,12 @@ que $ax \equiv 1[n]$.
 \begin{itemize}
 \item[\textbf{Existence.}]
 Comme $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout,
 \begin{itemize}
 \item[\textbf{Existence.}]
 Comme $a$ et $n$ sont premiers entre eux, d'après le théorème de Bézout,

-il existe $x$ et $y$ entiers tels que 
-PREUVE A FINIR
-
-
+il existe $x$ et $y$ entiers tels que $ax+ny = 1$, soit encore $ax \equiv 1[n]$.
+\item [\textbf{Unicité.}]
+Supposons qu'il existe une seconde solution $x'\in \{1, \dots, n-1\}$ telle que 
+$ax' \equiv 1[n]$. Donc $a(x-x') \equiv 0[n]$. Or $n$ est premier avec  $a$.
+D'après le théorème de Gau{\ss}, $n$ divise donc $x-x'$.
+Or $x-x'\in \{-n+2,-n+3,\dots,-1,0,1, \dots, n-2\}$. Le seul nombre divisible par $n$ est 0 et donc $x=x'$.

 \end{itemize} 
 \end{Proof}
 
 \end{itemize} 
 \end{Proof}
 


@@ -390,7 +403,7 @@ que  $7t -36u = 1$, soit encore les coefficient de Bézout relatifs à
 36 & = & 7  \times 5 +1 \\ 
 7 & = & 7 \times 1 + 0 \\
 & \textrm{et donc}&\\
 36 & = & 7  \times 5 +1 \\ 
 7 & = & 7 \times 1 + 0 \\
 & \textrm{et donc}&\\

-1 & = & 36 - 7 \time 5
+1 & = & 36 - 7 \times 5

 \end{eqnarray*}
 et donc $t = -5$ (et $u=-1$). 
 On en déduit $7x \equiv -11 [36]$ est équivalent à 
 \end{eqnarray*}
 et donc $t = -5$ (et $u=-1$). 
 On en déduit $7x \equiv -11 [36]$ est équivalent à 


@@ -407,12 +420,12 @@ $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  $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$, $3n + 7$ est divisible par 11
+\item  Trouvez pour quelles valeurs de $n$, $3^n + 7$ est divisible par 11.

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 


@@ -426,7 +439,8 @@ il existe une unique clé de décodage entre 1 et $\varphi(n)$.
 \end{Exo}
 
 \begin{Prop}[Théorème d'Euler]\label{th:Euler}
 \end{Exo}
 
 \begin{Prop}[Théorème d'Euler]\label{th:Euler}

-  Si $m<n$ est  relativement premier avec $n$, alors 
+Soit $n \in \N^*$ et $m$, $m<n$ un entier relativement premier avec $n$.
+Alors 

 \begin{equation}
 m^{\varphi(n)}\equiv1 [n].
 \end{equation}
 \begin{equation}
 m^{\varphi(n)}\equiv1 [n].
 \end{equation}


@@ -444,16 +458,42 @@ le message initial : $a^d \equiv m [n]$.
 \begin{Proof}
 \begin{eqnarray*}
 a^d & \equiv &   (m^e)^d [n]\\
 \begin{Proof}
 \begin{eqnarray*}
 a^d & \equiv &   (m^e)^d [n]\\

-& \equiv &   m^{ed} [n] (\textrm{ réécriture})\\
-& \equiv &   m^{k.\varphi(n)+1} [n] (\textrm{ définition de $d$})\\
-& \equiv &   m^{k.\varphi(n)}m [n] (\textrm{ réécriture})\\
-& \equiv &   (m^{\varphi(n)})^km [n] (\textrm{ réécriture})\\
-& \equiv &   (1)^km [n] (\textrm{ théorème d'Euler})\\
-& \equiv &   m [n] (\textrm{ réécriture})\\
+& \equiv &   m^{ed} [n] \textrm{ (réécriture)}\\
+& \equiv &   m^{k.\varphi(n)+1} [n] \textrm{ (définition de $d$)}\\
+& \equiv &   m^{k.\varphi(n)}m [n] \textrm{ (réécriture)}\\
+& \equiv &   (m^{\varphi(n)})^km [n] \textrm{ (réécriture)}\\
+& \equiv &   (1)^km [n] \textrm{ (théorème d'Euler)}\\
+& \equiv &   m [n] \textrm{ (réécriture)}\\

 \end{eqnarray*}
 \end{Proof}
 
 
 \end{eqnarray*}
 \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]$.


@@ -466,24 +506,25 @@ La preuve se fait par récurrence sur $a$.
 \item Supposons la formule établie pour $k=a$ et montrons qu'elle l'est aussi
 pour $k=a+1$. 
 On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient 
 \item Supposons la formule établie pour $k=a$ et montrons qu'elle l'est aussi
 pour $k=a+1$. 
 On remarque tout d'abord que pour chaque $k$, $0 < k < p$, le coefficient 

-binomial $\binom{p}{k} = \frac{p!}{k!(p-k)!}$ est divisible par $p$, c.-à-d.
+binomial $\binom{p}{k} = \dfrac{p!}{k!(p-k)!}$ est divisible par $p$, c.-à-d.

 $\binom{p}{k} \equiv 0 [p]$.
 On a alors successivement:
 \begin{eqnarray*}
 (k+1)^p &=& a^p + 
 \binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\
 &\equiv& a^p +1 [p]\textrm{ (d'après la remarque sur les coeff. binomiaux)}\\\
 $\binom{p}{k} \equiv 0 [p]$.
 On a alors successivement:
 \begin{eqnarray*}
 (k+1)^p &=& a^p + 
 \binom{p}{1}a^{p-1}+\binom{p}{2}a^{p-2}+\dots +\binom{p}{p-1}a^{1}+1\\
 &\equiv& a^p +1 [p]\textrm{ (d'après la remarque sur les coeff. binomiaux)}\\\

-&\equiv& a +1 [p]\textrm{ (par hypothèse de récurrence)}\\\
+&\equiv& a +1 [p]\textrm{ (par hypothèse de récurrence).}\\\

 \end{eqnarray*}
 \end{eqnarray*}

+\end{itemize}

 \end{Proof}
 
 \begin{Prop}[Corrolaire du petit théorème de Fermat]
 Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
 \end{Proof}
 
 \begin{Prop}[Corrolaire du petit théorème de Fermat]
 Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,

-alors $a^{p-1}-1$ est un multiple de $p$,
+alors $a^{p-1}-1$ est un multiple de $p$.

 \end{Prop}
 \begin{Proof}
 \end{Prop}
 \begin{Proof}

-D'après le petit théorèmede Fermat, $a^{p}  \equiv a [p]$. Dit Autrement
-$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ ne divise pas $a$ d'après les 
+D'après le petit théorème de Fermat, $a^{p}  \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec  $a$ d'après les 

 hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
 \end{Proof}
 
 hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
 \end{Proof}
 


@@ -496,29 +537,34 @@ On a successivement:
 666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\ 
  & \equiv & 3^{999} [13]\\ 
  & \equiv & 3^{12\times83 +3} [13] \\
 666^{999} & \equiv & (13\times 51 + 3)^{999} [13]\\ 
  & \equiv & 3^{999} [13]\\ 
  & \equiv & 3^{12\times83 +3} [13] \\

- & \equiv & 3^3 \time (3^{12})^{83} [13] \\
- & \equiv & 3^3 \time (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'après le corollaire du petit théorème de Fermat)}\\ 
+ & \equiv & 3^3 \times (3^{12})^{83} [13] \\
+ & \equiv & 3^3 \times (1)^{83} [13] \textrm{(car $3^{12}\equiv 1 [13]$ d'après le corollaire du petit théorème de Fermat)}\\ 

  & \equiv & 27 [13]\\
  & \equiv & 1 [13]
 \end{eqnarray*} 
 \end{Exp}
 
 
  & \equiv & 27 [13]\\
  & \equiv & 1 [13]
 \end{eqnarray*} 
 \end{Exp}
 
 

+

 \begin{Exo}
 \begin{Exo}

-Montrer que l'entier naturel $n$ est premier si et seulement si 
-$$(x +1) ^n \equiv x ^n +1[n].$$
+Calculer $2^{500} [13]$ et $26^{1000} [17]$.

 \end{Exo}
 
 
 \end{Exo}
 
 

+\begin{Exo}
+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.

 
 

-\begin{Exo}
-Calculer $2^{500} [13]$ et $26^{1000} [17]$.

 \end{Exo}
 
 
 \end{Exo}
 
 

+
+
+

 \section{Génération de grands nombres premiers}
 \section{Génération de grands nombres premiers}

-Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers.
+Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombres premiers.

 Depuis Euclide, on sait que $\Prem$ est de taille infinie.
 Fermat avait cru donner une formule ne générant que des nombres premiers.
 Il affirmait que pour tout $n \in \N$, le nombre 
 Depuis Euclide, on sait que $\Prem$ est de taille infinie.
 Fermat avait cru donner une formule ne générant que des nombres premiers.
 Il affirmait que pour tout $n \in \N$, le nombre 


@@ -526,19 +572,19 @@ Il affirmait que pour tout $n \in \N$, le nombre
 F_n &= & 2^{2^n} +1 
 \end{eqnarray}
 était premier. Or 641 divise $F_5$. Aujourd'hui, on pense que seuls 
 F_n &= & 2^{2^n} +1 
 \end{eqnarray}
 était premier. Or 641 divise $F_5$. Aujourd'hui, on pense que seuls 

-les nombres de $F_0$ à $F_4$ sont premiers, les qutres étant composés.
+les nombres de $F_0$ à $F_4$ sont premiers.

 
 

-\subsection{Distribution des nombres premier parmi les entiers}
+\subsection{Distribution des nombres premiers parmi les entiers}

 
 Même si on ne connaît pas de formule permettant de construire tous les 
 nombres premiers, tout n'est pas perdu puisque les nombres premiers 
 
 Même si on ne connaît pas de formule permettant de construire tous les 
 nombres premiers, tout n'est pas perdu puisque les nombres premiers 

-ne sont pas si rares que cela. Le théorème suivant donne même la distribution 
+ne sont pas si rares que cela. Le théorème suivant donne même 

 la proportion approximative des entiers inférieurs ou égaux à
 $N$  qui sont premiers.
 \begin{Prop}[Théorème des nombres premiers]
 La fonction $\pi:\N \rightarrow \N$  associe 
 la proportion approximative des entiers inférieurs ou égaux à
 $N$  qui sont premiers.
 \begin{Prop}[Théorème des nombres premiers]
 La fonction $\pi:\N \rightarrow \N$  associe 

-à chaque nombre $n$ nombre d'entiers inférieurs ou égaux à $n$ qui sont 
-premiers, soit $\pi(N) = |\{p \le N | p \textrm{premier}\}|$.
+à chaque nombre $N$ le nombre d'entiers inférieurs ou égaux à $N$ qui sont 
+premiers, soit $\pi(N) = |\{p \le N | p \textrm{ premier}\}|$.

 Lorsque $n$ est grand, on a:
 \begin{eqnarray}
 \pi(N) &\approx& \dfrac{N}{\ln(N)}
 Lorsque $n$ est grand, on a:
 \begin{eqnarray}
 \pi(N) &\approx& \dfrac{N}{\ln(N)}


@@ -588,7 +634,7 @@ Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 2
 \hline
  \end{tabular}
 \end{center}
 \hline
  \end{tabular}
 \end{center}

-\caption{Probabilités inverse d'obtenir un \label{Table:propPrem}}
+\caption{Probabilités inverse d'obtenir un nombre premier \label{Table:propPrem}}

 \end{table}
 
 
 \end{table}
 
 


@@ -610,7 +656,7 @@ de la primalité d'un entier, ce que présente la section suivante.
 
 
 \subsection{Tests de primalité}
 
 
 \subsection{Tests de primalité}

-Chque section donne un algorithme permettant de décider si un entier $p$ fourni
+Chaque section donne un algorithme permettant de décider si un entier $p$ fourni

 en entrée est premier ou non.
 
 \subsubsection{Méthode naïve}
 en entrée est premier ou non.
 
 \subsubsection{Méthode naïve}


@@ -621,7 +667,7 @@ calculer à l'avance une liste des nombres premiers inférieurs à $\sqrt{p}$
 (avec un crible d'Ératosthène), pour ne tester que ceux-ci.
 
 Par exemple, pour tester un nombre inférieur à 39 000, 
 (avec un crible d'Ératosthène), pour ne tester que ceux-ci.
 
 Par exemple, pour tester un nombre inférieur à 39 000, 

-il suffit de vérifier  qu'il nest pas multiple d'un nombre premiers inférieur
+il suffit de vérifier  qu'il n'est pas multiple d'un nombre premiers inférieur

 à 198 (car $198^2 = 39 204$); on doit faire au maximum 45 divisions.
 
 \subsubsection{Tests probabilistes}
 à 198 (car $198^2 = 39 204$); on doit faire au maximum 45 divisions.
 
 \subsubsection{Tests probabilistes}


@@ -646,33 +692,65 @@ Le petit théorème de Fermat est une implication et non pas une équivalence:
 \item rien ne dit non plus que que si on a  $a^{p-1}\equiv 1 [p]$ et que $a$ non divisible par $p$, alors $p$ est premier.
 \end{itemize}
 Cependant si on effectue un grand nombre de fois l'expérience de choisir 
 \item rien ne dit non plus que que si on a  $a^{p-1}\equiv 1 [p]$ et que $a$ non divisible par $p$, alors $p$ est premier.
 \end{itemize}
 Cependant si on effectue un grand nombre de fois l'expérience de choisir 

-$a \in \N_{n-1}^{*}$ et qu'à chaque foit on établit $a^{p-1}\equiv 1 [p]$, 
+$a \in \N_{n-1}^{*}$ et qu'à chaque fois on établit $a^{p-1}\equiv 1 [p]$, 

 alors $p$ est probablement premier.
 Cependant ce n'est pas toujours le cas: par exemple $2^{340} \equiv 1 [341]$ et 
 pourtant $341 =  11 \times 31$.
 
 \begin{Exo}
 alors $p$ est probablement premier.
 Cependant ce n'est pas toujours le cas: par exemple $2^{340} \equiv 1 [341]$ et 
 pourtant $341 =  11 \times 31$.
 
 \begin{Exo}

-Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne \verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{p}-1}\equiv 1 [\texttt{p}]$ pour un  
+Donner le code de la fonction \verb+testPrimaliteFermat(n,t)+ qui retourne 
+\verb+True+ si \verb+t+ evaluations de $\texttt{a}^{\texttt{p}-1}$ on retourné $ 1 [\texttt{p}]$ 
+pour un $a \in \N_{n-1}^{*}$ et \verb+False+ sinon.

 \end{Exo}
 
 
 
 \end{Exo}
 
 
 

-\paragrpah{Test de Miller-Rabin}
+\paragraph{Test de Miller-Rabin}

 
 

-\section{Factorisation}
+Soit $n$ un nombre premier impair,
+alors nous pouvons écrire $n - 1$ comme $2^s \times d$, 
+où $s$ est un entier et $d$ est impair.
+Alors, pour tout entier naturel $a \in \N_{n-1}^*$
+tel que $a$ est premier avec $n$, 
+une des conditions suivantes doit être vérifiée:
+\begin{enumerate}
+\item $a^{d} \equiv 1 [n]$, ou bien  
+\item $a^{2^r\cdot d} \equiv -1 [n]$ pour un certain $0 \le r \le s-1$.
+\end{enumerate} 
+La preuve de cette propriété est admise
+
+Le test de primalité de Miller-Rabin est basé sur les équations précédentes.
+Si on choisit un grand nombre $t$ de fois $a \in \N_{n-1}^*$
+et qu'on obtienne à chaque fois 
+\begin{itemize}
+\item $a^{d} \equiv 1 [n]$ ou 
+\item $a^{2^r\cdot d} \equiv -1 [n]$ pour un certain $0 \le r \le s-1$,
+\end{itemize}
+alors le nombre $n$ est probablement premier.
+Dans le cas contraire ($a^{d} \not\equiv 1 [n]$ et 
+$a^{2^r \cdot d} \not\equiv -1 [n]$ pour tous les  $0 \le r \le s-1$),
+$n$ n'est pas premier.

 
 

+\begin{Exo}
+Donner le code de la fonction \verb+testPrimaliteMillerRabin(n,t)+.
+\end{Exo}
+
+
+\section{Factorisation}
+L'objectif de cette partie est de montrer qu'on peut factoriser $n$ 
+sous la forme de $p\times q$ si ces deux derniers nombres ont été mal choisis.

 
 
 \begin{Exo}
 
 
 \begin{Exo}

-On considère que l'étape 1 de l'algorithme RSA a généré deux nombre premiers $p$ et $q$ tels que $p>q$. On definit  $t = \frac{p+q}{2}$ et $s = \frac{p−q}{2}$.
+On considère que l'étape 1 de l'algorithme RSA a généré deux nombre premiers $p$ et $q$ tels que $p>q$. On définit  $t = \frac{p+q}{2}$ et $s = \frac{p-q}{2}$.

 Montrer que
 \begin{enumerate}
 Montrer que
 \begin{enumerate}

-\item le produit $n = pq = t^2 − s^2$;
+\item le produit $n = pq = t^2 - s^2$;

 \item l'entier $t$ est légèrement supérieur à la racine carrée de $n$ et que $s $ est petit;
 \item l'entier $t$ est légèrement supérieur à la racine carrée de $n$ et que $s $ est petit;

-\item l'on peut utiliser ces informations pour factoriser $n$ c.-à-d. retrouver $p$ et $q$.
-\item Factoriser 9623827 et  343570291, % res=2953*3259     res = 17729*19379
+\item l'on peut utiliser ces informations pour factoriser $n$ c.-à-d. retrouver $p$ et $q$;
+\item Factoriser 9623827 et  343570291. % res=2953*3259     res = 17729*19379

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 

-\section{Conclusion}
-cf SMATH paragraphe applications p 223.
\ No newline at end of file
+% \section{Conclusion}
+% cf SMATH paragraphe applications p 223.
\ No newline at end of file