From ce66af1c68a5fe38e96bb47ebe7ae138fb914f9d Mon Sep 17 00:00:00 2001
From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?=
 <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Fri, 5 Sep 2014 13:36:32 +0200
Subject: [PATCH] avant soummission

---
 main.tex |   4 +-
 rsa.tex  | 175 +++++++++++++++++++++++++++++++++++++++----------------
 2 files changed, 126 insertions(+), 53 deletions(-)

diff --git a/main.tex b/main.tex
index 41c38f3..244a854 100755
--- a/main.tex
+++ b/main.tex
@@ -133,9 +133,9 @@ showstringspaces=false}     % no special string spaces
 
 
 \begin{document}
-\title{Modélisation mathématique}
+\title{DUT Informatique, modélisation mathématique, S3, M3202C}
 \author{Jean-Fran\c{c}ois {\sc Couchot} \\
-  \url{couchot [arobase]univ-fcomte
+  \url{jean-francois [point] couchot [arobase] univ-fcomte
     [point] fr}}
 
 
diff --git a/rsa.tex b/rsa.tex
index 7301393..0316be6 100644
--- 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 \\
-  & = & 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 \\
-& = & \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}
@@ -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}
-\varphi(pq)=(p-1)(q-1) \label{FEuler}
+\varphi(pq)=(p-1)(q-1). \label{FEuler}
 \end{equation} 
-
 \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$.
@@ -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$ 
@@ -294,6 +297,38 @@ 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}
+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 
@@ -334,7 +369,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.
@@ -360,7 +395,7 @@ Démontrer la proposition précédente.
 \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]$.
@@ -370,10 +405,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,
-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}
 
@@ -390,7 +427,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}&\\
-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 à 
@@ -412,7 +449,7 @@ $261x +2$ soit multiple de 305.
                                         $35k +r \equiv 3r [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}
 
@@ -426,7 +463,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}
-  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}
@@ -444,12 +482,12 @@ le message initial : $a^d \equiv m [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}
 
@@ -466,24 +504,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 
-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)}\\\
-&\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{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$,
-alors $a^{p-1}-1$ est un multiple de $p$,
+alors $a^{p-1}-1$ est un multiple de $p$.
 \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}
 
@@ -496,14 +535,20 @@ On a successivement:
 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}
 
 
+
+\begin{Exo}
+Calculer $2^{500} [13]$ et $26^{1000} [17]$.
+\end{Exo}
+
+
 \begin{Exo}
 Montrer que l'entier naturel $n$ est premier si et seulement si 
 $$(x +1) ^n \equiv x ^n +1[n].$$
@@ -512,13 +557,9 @@ $$(x +1) ^n \equiv x ^n +1[n].$$
 
 
 
-\begin{Exo}
-Calculer $2^{500} [13]$ et $26^{1000} [17]$.
-\end{Exo}
-
 
 \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 
@@ -526,19 +567,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 
-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 
-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 
-à 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)}
@@ -588,7 +629,7 @@ Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 2
 \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}
 
 
@@ -610,7 +651,7 @@ de la primalité d'un entier, ce que présente la section suivante.
 
 
 \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}
@@ -621,7 +662,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, 
-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}
@@ -646,33 +687,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 
-$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}
-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}
 
 
 
-\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}
-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}
-\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'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}
 
-\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
-- 
2.39.5