\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, 17 décembre 2009 (14\string:00 -- 17\string:00)}

\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},
\kbd{\emph{login}2.gp}, etc.

\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^{51} - 323,\quad 
10^{101} - 203,\quad
10^{199} - 9.\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$. 
\Qqq Écrire un programme trouvant le nombre premier $p$ le plus proche de $m-1$.
\qq 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 $m = 2009$.
Quelle est la structure de $E(\FM_p)$ ?

\Qqq Même question pour $m = 17122009$. On étudie maintenant cette courbe
$E$.
\qq Trouver un point $P$ d'ordre maximal $o$ dans $E(\FM_p)$.
\qq Ecrire un programme de calcul de log discret de base $P$, i.e.~qui pour
$Q\in \gen{P}$ retourne l'unique $x\in \ZM/o\ZM$ tel que $Q = [o]P$.

\exo On \emph{admet} que pour toute courbe elliptique $E/\FM_p$ on a
$$\#E(\FM_{p^k}) = p^k + 1 - \alpha^k - \beta^k,\quad k\geq 1,$$
où $\alpha,\beta$ sont les deux racines complexes d'un
polynôme quadratique $X^2 - s X + p$, $s\in \ZM$.

\Q D'après le cours, quelle inégalité vérifie $s$ ?

\Q Soit $E$ la courbe elliptique d'équation $y^2 = x^3 + 1$ sur $\FM_5$.
Compter naïvement les points de $E$ dans $\FM_{5^k}$ pour $k = 1, 2,\dots,
10$. 

\Q Écrire la formule générale pour $\#E(\FM_{5^k})$ et la simplifier.

\Q Donner la structure de $E(\FM_{5^k})$ pour $k\leq 10$.

%\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}
