\documentclass[11pt]{amsart}
\usepackage{kbexo}
\course{MHT911 -- Algorithmique}
\DeclareMathOperator{\Rem}{mod}
\def\kbd#1{\texttt{#1}}
\def\pow{\^{}\hskip0pt}
\def\thepage{}

\begin{document}
\pbtitle{Examen, 19 décembre 2008 (8\string:30 -- 11\string:30)}

\smallskip
\centerline{\bf  Durée 3 heures. Notes de cours et programmes GP autorisés.}
\bigskip

\noindent La clarté des programmes et la pertinence des commentaires est un
élément important d'appréciation. 
\begin{itemize}
\item Créer un fichier par exercice, intitulés \kbd{\emph{login}1.gp}
et \kbd{\emph{login}2.gp}.

\item Pour rendre votre copie, taper \url{~kbelabas/copie} dans un terminal,
depuis le répertoire où se trouvent vos fichiers. (Vous pouvez rendre
plusieurs fois votre copie: seule la dernière fait foi, les précédentes
sont détruites.)
\end{itemize}

\exo Donner une preuve de primalité ($p-1$ ou méthode des courbes elliptiques)
des entiers $N$ suivants:
$$ 10^{50} - 57,\quad 
10^{100} - 797,\quad
10^{200} - 189.\quad
$$

\exo On fixe un entier $m$, dont on désire qu'il soit le cardinal d'une
courbe elliptique $E$ sur un corps fini $\FM_p$. 
\Q Écrire un programme trouvant le nombre premier $p$ le plus proche de $m-1$.
\Q Lui faire vérifier que la borne de Hasse n'exclut pas qu'il existe
$E/\FM_p$ de cardinal $m$.
\Q Écrire un programme naïf, tirant $E$ au hasard jusqu'à ce que $\#E(\FM_p)
= m$.
\Q Trouver une courbe $E$ explicite de cardinal $2008$.
Quelle est la structure de $E(\FM_p)$ ?

\Q Même question avec $\#E(\FM_p) = 2009$.

\exo Soit $E$ la courbe elliptique d'équation $y^2 = x^3 + 1$.
\Q Soit $p = 10^{15}-11$ (qui est premier) et on considère $E$ sur $\FM_p$
\qq Trouver un point $P$ d'ordre $p+1$ dans $E(\FM_p)$. 
\qq En déduire le cardinal $\#E(\FM_p)$.
\qq Soit $Q$ l'un des deux points d'abscisse $4$ sur $E$, trouver l'entier
 $n$ (modulo $p+1$) tel que $Q = [n] P$. \hint{Une méthode de Shanks directe
sera coûteuse. Par contre, $p+1$ est friable.}

\exo Construire explicitement une implantation minimale du protocole ElGammal
(chiffrement et déchiffrement) basée sur une courbe elliptique "sure" de
cardinal $\sim 2^{160}$. On ne se préoccupera pas d'assurer l'intégrite ou
l'authenticité du message (via fonctions de hachage, etc.).
\end{document}
