\documentclass[12pt]{amsart}
\usepackage{kbexo}

\num{7}
\course{MHT203 -- Cryptologie}

\begin{document}

\exotitle[Petit  théorème de Fermat]

\exo
Si $p$ est premier, on a $a^{p-1} = 1\bmod{p}$ pour tout
$a$ premier avec $p$. La réciproque est fausse: il existe des entiers $n$ non
premiers, pour lesquels l'égalité $a^{n-1} = 1\bmod{n}$ est vérifiée pour tout
$a$ premier avec $n$; ce sont les \emph{nombres de Carmichael} (il en existe
une infinité). 

\Q Décomposer $561$ en produit de facteurs premiers.

\Q Montrer que, si $a$ est premier avec $561$, alors :
$$
a^{560} \equiv 1 \bmod{3},\quad
a^{560} \equiv 1 \bmod{11},\quad
a^{560} \equiv 1 \bmod{17}.
$$

\hint{Utiliser le théorème de Fermat!}

\Q Montrer que, pour tout $a$ premier avec $561$, on a $a^{560} = 1\bmod{561}$. 

\exo
Déterminer l'ordre des éléments de $(\ZM/ 7\ZM)^*$ et vérifier le théorème de
Fermat.

\exo

\Q Calculer modulo 100 : $6^2, 6^{2^2},   6^{2^3} ,  6^{2^4}, 6^{2^5}, 6^{2^6}$.
On pourra utiliser $ 6^{2^{k+1}}= \big(6^{2^k}\big)^2$.

\Q Calculer modulo 100 : $ 6^{73}$. \hint{Remarquer que $73=1+2^3+2^6$.}

\exo

\Q Ecrire 340 en base 2.

\Q En utilisant la méthode de l'exponentiation rapide, calculer modulo 340
$3^{2^k}$ pour $k=1,\dots,8$. En déduire que $3^{340} \equiv
56\bmod{341}$. L'entier 341 est-il premier ?

\exo
On veut calculer $x^k$ avec $x\in \ZM$ et $k\in \ZM_{>0}$. 

\Q On applique la méthode suivante :

\qq Ecrire l'entier $k$ en base $2$ 
$$ k=\sum_{0\leq i\leq q} a_i 2^i= \overline{a_qa_{q-1}\dots a_1a_0},
\quad
\text{avec $a_q=1$ et $a_i\in\set{0,1}$}.
$$
\qq Dans cette écriture, remplacer $1$ par $CM$ et $0$ par $C$. On
obtient une suite de $C$ et de $M$, qui commence par $CM$ puisque
$a_q=1$.

\qq On initialise $z\leftarrow 1$; puis on lit la suite de gauche à
droite: si on lit $C$ (resp.~$M$) on remplace $z\leftarrow z^2$ (resp.~$z
\leftarrow z\times x$).

\Q Vérifier que l'on obtient $z = x^k$ à la fin de l'algorithme

\Q Calculer avec cette méthode $54^{13}\bmod{59}$ et $563^{1234} \bmod{612}$. 
\end{document}

