à la figure~\ref{Fig:schemageneral}.
\begin{figure}[ht]
\begin{center}
+%\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}
\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}\\
-r_{n-1} & = & r_{n} \times q_{n+1} + 0
+r_{n-1} & = & r_{n} \times q_{n+1} + 0 \nonumber
\end{eqnarray}
& = & (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{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}
\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}
\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
%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)$.
-\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}
\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$.}
\end{enumerate}
\end{enumerate}
\end{Exo}
+
+
+
\section{Arithmétique modulaire}
-% cf TD maths discrète;
-% Corollaire 7.6 du chap RSA
-% unicité de la clef de décodage
+\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 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}
+\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}
+
+
+
+
+\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]\label{th: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}
+
+
+\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
+$$(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.
+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),
+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.
+
+%% 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}
+
+
+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é}
+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}
+
+\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
