\documentclass[11pt]{amsart}
\usepackage{kb}
\usepackage{kbexo}
\course{MHT814 -- Courbes Elliptiques}
\def\kbd#1{\texttt{#1}}
\def\thepage{}

\begin{document}
\pbtitle{Examen, Jeudi 23 Avril 2009 (14\string:00 -- 17\string:00)}

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

\noindent Clarté des programmes et pertinence des commentaires sont des
éléments importants d'appréciation. 
\begin{itemize}
\item Pour répondre aux questions, créer \emph{un} fichier par exercice,
intitulés \kbd{\emph{login}1.gp} et \kbd{\emph{login}2.gp}. Par exemple,
\kbd{kbelabas1.gp}. Toutes vos réponses manuscrites et vos résultats
numériques doivent être saisis sous forme de commentaires dans les
fichiers \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}
Vous pouvez utiliser les deux techniques suivantes:
\begin{itemize}
\item utiliser \kbd{allocatemem} pour augmenter la mémoire allouée à gp.

\item Vous pouvez compiler le fichier \kbd{nom.gp} et imprimer les
résultats dans le fichier \kbd{result} en exécutant la commande
\kbd{gp < nom.gp > result 2>\&1}.
\end{itemize}
\bigskip

\exo 

\Q Écrire un programme prenant en entrée un entier $k > 0$ et donnant en
sortie un nombre premier $p$ de $k$ bits (soit $2^{k-1} \leq p < 2^k$).

\Q Écrire un programme prenant en entrée un nombre premier $p$ et donnant en
sortie une courbe elliptique $E$ sur $\FM_p$ telle que $E(\FM_p)$
soit \emph{cyclique}, ainsi qu'un générateur de ce groupe.

\Q Écrire un ensemble de fonctions implantant un cryptosystème d'ElGamal sur
les points d'une courbe elliptique $E/\FM_p$ (chiffrement, déchiffrement,
signature).

\noindent \hint{On supposera que le message à transmettre est un point de
$E(\FM_p)$, et on omettra le hachage destiné à assurer l'intégrité du
message. Commenter le choix des paramètres.}

\exo Soit $E$ une courbe elliptique sur un corps fini $\FM_q$ où $q$ est un
nombre \emph{premier}. Soient $P,Q\in E(\FM_q)$, où $P$ est d'ordre $n$
et $Q$ est dans le sous-groupe engendré par $P$; on cherche à résoudre le
problème du logarithme discret:
$$ Q=[m]P, $$
où on désire déterminer $m\in\ZM/n\ZM$. On appelle \emph{ordre} du logarithme
discret l'ordre $n$ du point $P$.

\Q Soit $p$ un diviseur premier de $n$. La valeur de $m$ modulo $p$, notée
$m_1$, est donnée par la résolution du problème du logarithme discret
$$ Q_1=[m_1]P_1,\qquad\text{où}\quad
P_1 = \left[\frac{n}{p}\right]P,\quad Q_1 = \left[\frac{n}{p}\right]Q,
$$
et $P_1$ est d'ordre $p$. 

\qq On écrit la division euclidienne $m = p m_0 + m_1$ (où $m_1$ est
maintenant connu), montrer que $m_0$ est solution d'un problème de logarithme
discret d'ordre $n/p$.

\qq Implanter l'algorithme correspondant, en utilisant une fonction «boite
noire» capable de résoudre les logarithmes discrets d'ordre un nombre
premier.

\Q Soient $p=10^{18}+3$ et $E$ la courbe elliptique sur $\FM_p$
d'équation $y^2=x^3+2$.

\qq Calculer $\#E(\FM_p)$.

\qq Trouver un point $P_d\in E$ pour chacun des ordres possibles $d\mid
\#E(\FM_p)$.

\Q Montrer qu'il existe deux points d'abscisse $2$ dans $E(\FM_p)$. Quel sont
leurs ordres ? Choisissez l'un d'entre eux, noté $P$ dans la suite.

\Q Montrer que $Q = (6, 181579992970505432)$ est sur $E$.

\Q Résoudre le problème du logarithme discret sur $E$
$$ Q=[m]P. $$

\Q Trouver des valeurs de $p$, $E$, $P$, $Q$ pour lesquelles les programmes
écrits ci-dessus ont des difficultés. Expliquez-les.
\end{document}
