From 69c903a978a2ef5a25298c9ae3920be0d8c62e95 Mon Sep 17 00:00:00 2001
From: =?utf8?q?Jean-Fran=C3=A7ois=20Couchot?=
 <couchot@couchot.iut-bm.univ-fcomte.fr>
Date: Thu, 4 Sep 2014 16:02:45 +0200
Subject: [PATCH] factorisation

---
 rsa.tex      | 97 +++++++++++++++++++++++++++++++++++++++++++++++-----
 symboles.sty |  1 +
 2 files changed, 89 insertions(+), 9 deletions(-)

diff --git a/rsa.tex b/rsa.tex
index d9312ed..cb11f3f 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -391,7 +391,7 @@ Démontrer que si la clé d'encryptage est $e < \varphi(n)$, alors
 il existe une unique clé de décodage entre 1 et $\varphi(n)$.
 \end{Exo}
 
-\begin{Prop}[Théorème d'Euler]
+\begin{Prop}[Théorème d'Euler]\label{th:Euler}
   Si $m<n$ est  relativement premier avec $n$, alors 
 \begin{equation}
 m^{\varphi(n)}\equiv1 [n].
@@ -429,7 +429,8 @@ $$(x +1) ^n \equiv x ^n +1[n].$$
 
 
 \section{Génération de grands nombres premiers}
-Depuis Euclide, on sait qu'il y a une infinité de nombres premiers.
+Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs 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 
 \begin{eqnarray}
@@ -478,17 +479,11 @@ Dans celui-ci:
   les multiples de 5 ne sont pas premiers!
 \end{itemize}
 On constate que si l'on tire au hasard un nombre (même de 100 chiffres), 
-et que ce nombre se termine par$\{1,3,7,9\}$, 
+parmi ceux qui se terminent par $\{1,3,7,9\}$ (ensemble noté $B$ par la suite) 
 la probabilité qu'il soit premier n'est pas infime. La solution au problème 
 de génération de nombres premiers repose sur la capacité ou non a disposer 
 d'un test efficace de primalité pour des grands nombres.
 
-Pour peut qu'on dispose d'un test de primalité rapide,
- 
-
-il \og suffit \fg{}
-de tirer quelques nombres au hasard pour avoir  
-
 %% Attention ce tableau est généré par ailleurs 
 \begin{table}[ht]
 \begin{center}
@@ -507,12 +502,96 @@ Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 2
 \caption{Probabilités inverse d'obtenir un \label{Table:propPrem}}
 \end{table}
 
+
+On considère comme expérience aléatoire le fait de tirer un nombre au hasard 
+dans $B$. On a une probabilité $p$ que le nombre soit premier.
+Soit $X$ la variable aléatoire qui compte le nombre 
+de fois où l'on a réalisé cette expérience avant d'obtenir un nombre premier.
+$X$ suit une loi géométrique de paramètre $p$:
+\[
+P(X=k) = (1-p)^{k-1}p.
+\]
+Or l'espérance d'une variable aléatoire
+suivant une loi géométrique de paramètre $p$ est $\frac{1}{p}$.
+Pour 100 chiffres, il faudra en moyenne 92 tirages pour générer un 
+nombre premier. 
+
+Il \og reste \fg{} à fournir une méthode efficace pour décider 
+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
+en entrée est premier ou non.
+
+\subsubsection{Méthode naïve}
+On vérifie s'il est divisible par l'un des entiers pairs compris entre 2 et 
+$\sqrt{p}$. Si la réponse est négative, alors $p$ est premier, 
+sinon il est composé. Pour améliorer la performance de cette méthode, on peut 
+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
+à 198 (car $198^2 = 39 204$); on doit faire au maximum 45 divisions.
 
+\subsubsection{Tests probabilistes}
 
+\begin{Prop}[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$, c'est-à-dire:
+\begin{equation}
+ \forall a\in \N \forall p \in \N (   p \in \Prem \textrm{ et }   a \not\equiv  0[p] 
+  \Rightarrow a^{p-1}\equiv 1 [p]).
+\label{petittheremeFermat}
+\end{equation}
+\end{Prop}
+
+\begin{Proof}
+La preuve découle directement du théorème~\ref{th:Euler} d'Euleur.
+En effet on a successivement:
+\begin{eqnarray*}
+  a^{p-1} & =  & a^{\varphi(p)} \textrm{(comme p est premier)}\\
+  & \equiv  &  1 [p] \textrm{(théorème d'Euler)}
+\end{eqnarray*}
+\end{Proof}
+
+\paragraph{Test de Fermat.}
+Le petit théorème de Fermat est une implication et non pas une équivalence:
+\begin{itemize}
+\item si on prend un $p\in \N$ et un $a \in\N$ quelconque, 
+  alors si $p$ est premier et $a$ non divisible par $p$, alors on peut en déduire que $a^{p-1}\equiv 1 [p]$;
+\item rien ne dit que si on a  $a^{p-1}\equiv 1 [p]$, alors $p$ est premier et $a$ non divisible par $p$.
+\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]$, 
+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  
+\end{Exo}
+
+
+
+\paragrpah{Test de Miller-Rabin}
 
 \section{Factorisation}
 
 
+
+\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}$.
+Montrer que
+\begin{enumerate}
+\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
+\end{enumerate}
+\end{Exo}
+
 \section{Conclusion}
 cf SMATH paragraphe applications p 223.
\ No newline at end of file
diff --git a/symboles.sty b/symboles.sty
index 40d3100..ca8d292 100755
--- a/symboles.sty
+++ b/symboles.sty
@@ -86,6 +86,7 @@ depth\dimen2\box1\vrule}%
 \def\cmat{\hbox{\it l\hskip -5.5pt C\/}}
 
 \def\N{{\mathbb N}}
+\def\Prem{{\mathbb P}}
 \def\Net{{\mathbb N}^*}
 \def\Z{{\mathbb Z}}
 \def\Q{{\mathbb Q}}
-- 
2.39.5