+
+\begin{Exo}
+On considère l'algorithme suivant:
+on choisit deux nombres premiers $p$ et $q$
+distincts tels que
+$p \equiv 2 [3]$ et $s \equiv 2 [3]$.
+Soit $n = pq$.
+Alice veut envoyer un message à Bob.
+Comme dans RSA, son message est un nombre $m \in \ \{1, . . . , n - 1\}$
+tel que $m \land n = 1$
+Le message codé d'Alice est le résultat $a= m^3[n]$.
+Bob décode $a$ en calculant
+\[
+m' \equiv a^{d} [n] \textrm{ où $d=\dfrac{2(p-1)(q-1)+1}{3}$}
+\]
+Normalement $m$ doit être égal à $m'$.
+
+\begin{enumerate}
+\item Choisir $p=11$, $q=17$, $m=4$ puis construire le message codé ainsi que le message décodé.
+\item Montrer que $d$ est toujours un entier.
+\item Expliquer pourquoi $a$ et $m'$ ne sont pas divisibles par $n$.
+\item Montrer que Bob a bien décodé le message d’Alice.
+\end{enumerate}
+
+\end{Exo}
+
+
+\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} = \dfrac{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{itemize}
+\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ème de Fermat, $a^{p} \equiv a [p]$. Dit Autrement
+$p$ divise $a^{p} - a = a (a^{p-1}-1)$. Or $p$ est premier avec $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}
+
