From 6a1d659a8d09f1c48fe968a3d6b9941576e22dfe Mon Sep 17 00:00:00 2001
From: couchot <jf.couchot@gmail.com>
Date: Thu, 4 Sep 2014 08:25:33 +0200
Subject: [PATCH 1/1] debut premiers

---
 rsa.tex | 122 +++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 116 insertions(+), 6 deletions(-)

diff --git a/rsa.tex b/rsa.tex
index fae4839..d9312ed 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -24,8 +24,8 @@ Dans le cas où l'on utilise une clé de cryptage, on a le schéma présenté
 à la figure~\ref{Fig:schemageneral}.
 \begin{figure}[ht]
 \begin{center}
-\includegraphics[scale=0.5]{schemacrypto.pdf}
-%\includegraphics[scale=0.5]{schemacrypto.eps}
+%\includegraphics[scale=0.5]{schemacrypto.pdf}
+\includegraphics[scale=0.5]{schemacrypto.eps}
 \end{center}
 \caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
 \end{figure}
@@ -259,6 +259,7 @@ produit:
 \begin{equation}
 \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 
@@ -384,11 +385,39 @@ il exite $x$ et $y$ entiers tels que
 \end{enumerate}
 \end{Exo}
 
+\begin{Exo}
+On se place dans le contexte de cryptographie par RSA.
+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}
 
-% cf TD maths discrète; 
-% Corollaire 7.6 du chap RSA
-% unicité de la clef de décodage
-
+\begin{Prop}[Théorème d'Euler]
+  Si $m<n$ est  relativement premier avec $n$, alors 
+\begin{equation}
+m^{\varphi(n)}\equiv1 [n].
+\end{equation}
+\end{Prop}
+On laisse de côté la démonstration.
+
+\begin{Prop}[Correction de RSA]
+Le cryptage-décryptage du code RSA est correct: 
+on crypte un message $m$ tel que 
+$m\land n= 1$ en $a$ avec  
+$ m^e  \equiv a [n]$ selon la clé $(e,n)$.
+Alors le décryptage selon la clé $(d,n)$ redonne
+le message initial : $a^d \equiv m [n]$.
+\end{Prop} 
+\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})\\
+\end{eqnarray*}
+\end{Proof}
 
 \subsection{Puissance de grands nombres}
 
@@ -400,6 +429,87 @@ $$(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.
+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}
+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.
+
+\subsection{Distribution des nombres premier 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 
+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}\}|$.
+Lorsque $n$ est grand, on a:
+\begin{eqnarray}
+\pi(N) &\approx& \dfrac{N}{\ln(N)}
+\end{eqnarray}
+\end{Prop}
+La preuve de ce théorème est d'un niveau très avancé et n'est pas reproduite 
+ici.
+
+Pour obtenir un  entier de 100 chiffres, il suffit de considérer 
+$N= 10^{100}$. Si on choisit au hasard un nombre $n$ dans $\N_{N}^{*}$,
+la probabilité qu'il soit premier est: 
+\begin{eqnarray*}
+\textrm{Prob}(n \textrm{ premier}) &\approx&
+ \dfrac{\dfrac{N}{\ln(N)}}{N} \\
+ &\approx&
+ \dfrac{1}{\ln(N)}
+\end{eqnarray*}
+Le tableau~\ref{Table:propPrem} donne une valeur approchée de 
+cette probabilité pour quelques nombres de chiffres. 
+Dans celui-ci:
+\begin{itemize}
+\item la seconde ligne n'impose aucune restriction sur le dernier chiffre;
+\item la troisième ligne impose que le dernier chiffre soit dans 
+  $\{1,3,5,7,9\}$: il est  inutile de vérifier que les
+  multiples de 2 sont premiers!
+\item la quatrième ligne impose que le dernier chiffre soit dans $\{1,3,7,9\}$:
+  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\}$, 
+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}
+\begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
+ \hline 
+Nombre de chiffres & \textbf{75}& \textbf{100}& \textbf{125}& \textbf{150}& \textbf{175}& \textbf{200}& \textbf{225}& \textbf{250}& \textbf{275}& \textbf{300}\\
+\hline 
+Dernier chiffre quelconque & 172& 230& 287& 345& 402& 460& 518& 575& 633& 690\\
+\hline 
+Dernier chiffre impair & 86& 115& 143& 172& 201& 230& 259& 287& 316& 345\\
+\hline 
+Dernier chiffre dans $\{1,3,7,9\}$& 69& 92& 115& 138& 161& 184& 207& 230& 253& 276\\
+\hline
+ \end{tabular}
+\end{center}
+\caption{Probabilités inverse d'obtenir un \label{Table:propPrem}}
+\end{table}
+
+\subsection{Tests de primalité}
+
+
 
 \section{Factorisation}
 
-- 
2.39.5