X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/modelisationMathS3.git/blobdiff_plain/69c903a978a2ef5a25298c9ae3920be0d8c62e95..7d35709eec25c5d67b07004710bb49813f9c4477:/rsa.tex

diff --git a/rsa.tex b/rsa.tex
index cb11f3f..7301393 100644
--- a/rsa.tex
+++ b/rsa.tex
@@ -296,7 +296,8 @@ d'inconnues $x$ et $y$.
 
 
 \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$.}
@@ -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,
-il exite $x$ et $y$ entiers tels que 
+il existe $x$ et $y$ entiers tels que 
+PREUVE A FINIR
+
+
 \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}
@@ -385,6 +416,9 @@ 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 
@@ -419,8 +453,56 @@ a^d & \equiv &   (m^e)^d [n]\\
 \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}
 
+\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 
@@ -428,6 +510,13 @@ $$(x +1) ^n \equiv x ^n +1[n].$$
 \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.
@@ -537,7 +626,7 @@ il suffit de vÃ©rifier  qu'il nest pas multiple d'un nombre premiers infÃ©rieur
 
 \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}
@@ -547,14 +636,6 @@ alors $a^{p-1}-1$ est un multiple de $p$, c'est-Ã -dire:
 \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:
