ajout d'exos de congruences

[modelisationMathS3.git] / rsa.tex

diff --git a/rsa.tex b/rsa.tex
index d9312ed7c079960e1eceeb3c6471b28f61f1dbe1..7301393245b4f6db9167b3f03d93acbcba967a68 100644 (file)
--- a/rsa.tex
+++ b/rsa.tex
@@ -296,7 +296,8 @@ d'inconnues $x$ et $y$.
 
 
 \begin{Exo}[Sujet du bac S Liban 2005]
 
 
 \begin{Exo}[Sujet du bac S Liban 2005]

-On rappelle le résultat suivant appelé petit théorème de Fermat.
+On rappelle le résultat suivant appelé le corollaire du 
+petit théorème de Fermat.

 
 \emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
  alors $a^{p-1}-1$ est un multiple de $p$.}
 
 \emph{Si $p$ est un nombre premier et $a$ un entier non divisible par $p$,
  alors $a^{p-1}-1$ est un multiple de $p$.}


@@ -369,10 +370,40 @@ 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 exite $x$ et $y$ entiers tels que 
+il existe $x$ et $y$ entiers tels que 
+PREUVE A FINIR
+
+

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

+\begin{Exp}
+Trouvons les nombres $x$ tels que $7x+11$ soit multiple de 36. Dit autrement, 
+résoudre l'équation $7x \equiv -11 [36]$. 
+
+On cherche un \og inverse \fg{} de 7 c.-à-d. un nombre $t$, $1 < t < 35$ 
+tel que $7t \equiv 1 [36]$. 
+Soit à résoudre $7t \equiv 1 [36]$ qui revient à trouver $t$ et $u$ tels
+que  $7t -36u = 1$, soit encore les coefficient de Bézout relatifs à 
+(7 et 36). On trouve successivement 
+\begin{eqnarray*}
+36 & = & 7  \times 5 +1 \\ 
+7 & = & 7 \times 1 + 0 \\
+& \textrm{et donc}&\\
+1 & = & 36 - 7 \time 5
+\end{eqnarray*}
+et donc $t = -5$ (et $u=-1$). 
+On en déduit $7x \equiv -11 [36]$ est équivalent à 
+$(-5).7x \equiv (-5).-11 [36]$ soit encore 
+$x \equiv 55 [36] \equiv 19 [36]$.
+\end{Exp}
+
+\begin{Exo}
+Trouver les entiers relatif $x$ tels que 
+$261x +2$ soit multiple de 305.
+\end{Exo}
+
+

 
 \begin{Exo}
 \begin{enumerate}
 
 \begin{Exo}
 \begin{enumerate}


@@ -385,13 +416,16 @@ il exite $x$ et $y$ entiers tels que
 \end{enumerate}
 \end{Exo}
 
 \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}
 
 \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}
 

-\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].
   Si $m<n$ est  relativement premier avec $n$, alors 
 \begin{equation}
 m^{\varphi(n)}\equiv1 [n].


@@ -419,8 +453,56 @@ a^d & \equiv &   (m^e)^d [n]\\
 \end{eqnarray*}
 \end{Proof}
 
 \end{eqnarray*}
 \end{Proof}
 

+
+\begin{Prop}[Petit théorème de Fermat]
+Si $p$ est un nombre premier et $a$ un entier 
+alors $a^{p} \equiv a [p]$.
+\end{Prop}
+
+\begin{Proof}
+La preuve se fait par récurrence sur $a$. 
+\begin{itemize}
+\item Pour $a=0$, c'est trivial.
+\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.
+$\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)}\\\
+\end{eqnarray*}
+\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$,
+\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 
+hypothèses. D'après le théorème de Gau{\ss}, $p$ divise $a^{p-1}-1$.
+\end{Proof}
+

 \subsection{Puissance de grands nombres}
 
 \subsection{Puissance de grands nombres}
 

+\begin{Exp}
+Calculons $666^{999}[13]$.
+On a successivement:
+\begin{eqnarray*}
+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 & 27 [13]\\
+ & \equiv & 1 [13]
+\end{eqnarray*} 
+\end{Exp}
+

 
 \begin{Exo}
 Montrer que l'entier naturel $n$ est premier si et seulement si 
 
 \begin{Exo}
 Montrer que l'entier naturel $n$ est premier si et seulement si 


@@ -428,8 +510,16 @@ $$(x +1) ^n \equiv x ^n +1[n].$$
 \end{Exo}
 
 
 \end{Exo}
 
 

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

 \section{Génération de grands nombres premiers}
 \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}
 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 +568,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), 
   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.
 
 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}
 %% Attention ce tableau est généré par ailleurs 
 \begin{table}[ht]
 \begin{center}


@@ -507,12 +591,88 @@ 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}
 
 \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é}
 \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}[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$, 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}
+
+
+\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}
 
 
 \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
 \section{Conclusion}
 cf SMATH paragraphe applications p 223.
\ No newline at end of file