ajout d'exos de congruences

[modelisationMathS3.git] / rsa.tex

diff --git a/rsa.tex b/rsa.tex
index cb11f3fb69496ef14c61bbe992ee6c204aeed022..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,6 +416,9 @@ 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 
 \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 


@@ -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,6 +510,13 @@ $$(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}
 Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers.
 Depuis Euclide, on sait que $\Prem$ est de taille infinie.
 \section{Génération de grands nombres premiers}
 Dans ce qui suit, on nomme $\Prem$ l'ensemble des nombrs premiers.
 Depuis Euclide, on sait que $\Prem$ est de taille infinie.


@@ -537,7 +626,7 @@ il suffit de vérifier  qu'il nest pas multiple d'un nombre premiers inférieur
 
 \subsubsection{Tests probabilistes}
 
 
 \subsubsection{Tests probabilistes}
 

-\begin{Prop}[Petit théorème de Fermat]
+\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}
 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}


@@ -547,14 +636,6 @@ alors $a^{p-1}-1$ est un multiple de $p$, c'est-à-dire:
 \end{equation}
 \end{Prop}
 
 \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:
 
 \paragraph{Test de Fermat.}
 Le petit théorème de Fermat est une implication et non pas une équivalence: