ajout de calcul modulo

[modelisationMathS3.git] / rsa.tex

diff --git a/rsa.tex b/rsa.tex
index 541d3c233107e6b4fe0974db31b23b5e81e3d924..fae4839b4f6482cfb013246720a1ba16cb2b6d61 100644 (file)
--- a/rsa.tex
+++ b/rsa.tex
@@ -24,7 +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}
 à la figure~\ref{Fig:schemageneral}.
 \begin{figure}[ht]
 \begin{center}

-\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}
 \end{center}
 \caption{Schéma général d'une méthode de cryptage/décryptage}\label{Fig:schemageneral}
 \end{figure}


@@ -190,13 +191,13 @@ Dans la preuve de la proposition précédente, on avait successivement
 
 \begin{eqnarray}
 a &=& b \times q_1 +r_1 \label{eq:def:r1} \\
 
 \begin{eqnarray}
 a &=& b \times q_1 +r_1 \label{eq:def:r1} \\

-b &=& r_1 \times q_2 +r_2 \\
-r_1 &=& r_2 \times q_3 +r_3 \\
+b &=& r_1 \times q_2 +r_2 \nonumber \\
+r_1 &=& r_2 \times q_3 +r_3 \nonumber\\

 & \vdots & \nonumber\\
 r_{n-4} & = & r_{n-3} \times q_{n-2} + r_{n-2} \label{eq:def:rnm4} \\
 r_{n-3} & = & r_{n-2} \times q_{n-1} + r_{n-1} \label{eq:def:rnm3} \\
 r_{n-2} & = & r_{n-1} \times q_{n} + r_{n} \label{eq:def:rnm2}\\
 & \vdots & \nonumber\\
 r_{n-4} & = & r_{n-3} \times q_{n-2} + r_{n-2} \label{eq:def:rnm4} \\
 r_{n-3} & = & r_{n-2} \times q_{n-1} + r_{n-1} \label{eq:def:rnm3} \\
 r_{n-2} & = & r_{n-1} \times q_{n} + r_{n} \label{eq:def:rnm2}\\

-r_{n-1} & = & r_{n} \times q_{n+1} + 0 
+r_{n-1} & = & r_{n} \times q_{n+1} + 0 \nonumber 

 \end{eqnarray}
 
 
 \end{eqnarray}
 
 


@@ -209,15 +210,14 @@ r_{n}  & = & r_{n-2} - r_{n-1} \times q_{n}  \nonumber \\
    & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}(\textrm{on remplace $r_{n-2}$ par sa def dans (\ref{eq:def:rnm4})}) \nonumber \\
 & \vdots & \nonumber \\
 & = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\ 
    & = & (r_{n-4} - r_{n-3} \times q_{n-2}). (1 + q_{n-1}. q_{n}) - r_{n-3}. q_{n}(\textrm{on remplace $r_{n-2}$ par sa def dans (\ref{eq:def:rnm4})}) \nonumber \\
 & \vdots & \nonumber \\
 & = & \ldots (\textrm{on remplace $r_{1}$ par sa def dans (\ref{eq:def:r1})}) \nonumber\\ 

-& = ax + by \nonumber
+& = &ax + by \nonumber

 \end{eqnarray}
 \end{eqnarray}

-

 \end{Proof}
 
 
 
 \begin{Def}[Nombres premiers entre eux]
 \end{Proof}
 
 
 
 \begin{Def}[Nombres premiers entre eux]

-Les deux entiers relatifs $a$ et $b$ sont premiers entre eux s 
+Les deux entiers relatifs $a$ et $b$ sont premiers entre eux si 

 leur plus grand commun diviseur est égal à 1.
 \end{Def}
 
 leur plus grand commun diviseur est égal à 1.
 \end{Def}
 


@@ -237,7 +237,7 @@ car 1 est le PGCD de $a$ et de $b$.
 \item[\textbf{Si.}] 
   Supposons qu'il existe un couple $(x,y)$ 
   d'entiers relatifs vérifiant $ax + by = 1$ et $d = a \land b$.
 \item[\textbf{Si.}] 
   Supposons qu'il existe un couple $(x,y)$ 
   d'entiers relatifs vérifiant $ax + by = 1$ et $d = a \land b$.

-  Le $d$ divise $ax$ et $d$ divise $by$. Donc $d$ divise 
+  L'entier $d$ divise les produits $ax$ et $by$. Donc $d$ divise 

   $ax + by$ et donc $d$ est 1.   
 \end{itemize}
 \end{Proof}
   $ax + by$ et donc $d$ est 1.   
 \end{itemize}
 \end{Proof}


@@ -279,15 +279,15 @@ premiers avec $pq$.
 
 %Refaire cet exo avec 27x +8y = 1
 \begin{Exo}
 
 %Refaire cet exo avec 27x +8y = 1
 \begin{Exo}

-L'objectif est de résoudre l'équation $(E)$ d'inconnues $x$ et $y$ 
-$405x -120y =15$.
+L'objectif est de résoudre l'équation $(E)$ $405x -120y =15$ 
+d'inconnues $x$ et $y$.

 \begin{enumerate}
 \item Trouver le PGCD de 405 et 120  à l'aide de l'algorithme d'Euclide.
 \item En déduire une solution particulière de cette équation.
 \item En utilisant la solution particulière, montrer que $(E)$ est 
   équivalente à $27(x-3) = 8(y-10)$.
 \begin{enumerate}
 \item Trouver le PGCD de 405 et 120  à l'aide de l'algorithme d'Euclide.
 \item En déduire une solution particulière de cette équation.
 \item En utilisant la solution particulière, montrer que $(E)$ est 
   équivalente à $27(x-3) = 8(y-10)$.

-\item Utiliser le théorème de Gauss pour montrer que 
-  l'ensemble solution de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 
+\item Utiliser le théorème de Gau{\ss} pour montrer que 
+  l'ensemble des solutions de $(E)$ est $\{(8k+3;27k+10)| k \in \Z\}$. 

 \end{enumerate}
 \end{Exo}
 
 \end{enumerate}
 \end{Exo}
 


@@ -329,7 +329,62 @@ $g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
 \end{enumerate}
 \end{enumerate}
 \end{Exo}
 \end{enumerate}
 \end{enumerate}
 \end{Exo}

+
+
+

 \section{Arithmétique modulaire}
 \section{Arithmétique modulaire}

+
+\begin{Def}[Congruence modulo]
+Soit $a$ et $b$ deux entiers relatifs.
+On dit que $a$ est congru $b$ modulo $n$ si $n$ divise $a-b$, c'est-à-dire
+s'il existe $x \in \Z$ tel que $(a-b) = nx$.
+On note    $a \equiv b [n]$. 
+La relation \og $\equiv [n]$ \fg{}
+est une relation d'équivalence appelée congruence modulo $n$.
+\end{Def}
+
+\begin{Prop}
+Soit $a$, $b$, $c$, $d$, $x$ et $y$ dans $\Z$. 
+Si $a \equiv c[n]$ et  $b \equiv d[n]$, alors
+\begin{enumerate}
+\item $a +b \equiv c + d [n]$;
+\item $ab \equiv cd [n]$;
+\item $ax +by \equiv cx +dy [n]$.
+\end{enumerate}
+\end{Prop}
+
+\begin{Exo}
+Démontrer la proposition précédente.
+\end{Exo}
+
+\begin{Prop}
+Soit deux entiers naturels $a$ et $n$ tels que $a< n$.
+Si $a$ et $n$ sont premier entre eux, 
+alors il existe un unique $x \in \{1, \dots, n-1\}$ tel 
+que $ax \equiv 1[n]$.
+\end{Prop}
+
+\begin{Proof}
+\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 
+\end{itemize} 
+\end{Proof}
+
+
+\begin{Exo}
+\begin{enumerate}
+\item Démonter que $35 \equiv 1 [11]$
+\item En déduire que pour tous entiers naturels $k$ et $r$ on a 
+                                        $35k +r \equiv 3r [11]$.
+\item  $n$ étant un entier naturel, quels sont les restes possibles
+  dans la division de $3^n$ par 11?
+\item  Trouvez pour quelles valeurs de $n$, $3n + 7$ est divisible par 11
+\end{enumerate}
+\end{Exo}
+
+

 % cf TD maths discrète; 
 % Corollaire 7.6 du chap RSA
 % unicité de la clef de décodage
 % cf TD maths discrète; 
 % Corollaire 7.6 du chap RSA
 % unicité de la clef de décodage


@@ -337,6 +392,13 @@ $g(f(a))=a$ . Que peut-on dire de $f(g(a))=a$?
 
 \subsection{Puissance de grands nombres}
 
 
 \subsection{Puissance de grands nombres}
 

+
+\begin{Exo}
+Montrer que l'entier naturel $n$ est premier si et seulement si 
+$$(x +1) ^n \equiv x ^n +1[n].$$
+\end{Exo}
+
+

 \section{Génération de grands nombres premiers}
 
 \section{Factorisation}
 \section{Génération de grands nombres premiers}
 
 \section{Factorisation}