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

\begin{document}
\pbtitle{Devoir Surveillé, Jeudi 02 Avril 2009 (16\string:15 -- 18\string:15)}

\smallskip
\centerline{\bf  Durée 2 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 Pour répondre aux questions, créer \textbf{un} fichier par exercice,
intitulés \kbd{\emph{login}1.gp}, \kbd{\emph{login}2.gp}. Par exemple,
\kbd{gricotta1.gp}.

\item Pour rendre votre copie, taper \url{~gricotta/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}
\bigskip

\exo Une \textbf{représentation binaire signée} d'un entier relatif $n$ est la donnée d'un vecteur $S=\left[s_0,\dots,s_q\right]$ satisfaisant
\begin{equation*}
n=\sum_{j=0}^qs_j2^j
\end{equation*}
où $s_j\in\left\{-1,0,+1\right\}$ pour $0\leq j\leq q$. Une telle représentation binaire signée est dite \textbf{creuse} si
\begin{equation*}
\forall j\in\left\{0,\dots,q-1\right\},\quad s_js_{j+1}=0.
\end{equation*}
Vous \textbf{admettrez} que tout entier relatif admet une unique représentation binaire signée creuse.

\Q Ecrire une procédure \emph{basesignee(n)} qui, étant donné l'entier naturel $n$, renvoie la représentation binaire signée creuse de $n$ sous la forme d'un vecteur $S=[s_0,\dots,s_{q}]$. \textbf{\textit{Indication}}:
\begin{itemize}
\item
vous connaissez la représentation binaire de $n$;
\item
une procédure récursive devrait permettre de décaler vers la droite les bits consécutifs de $1$ dans cette représentation binaire de $n$ c'est-à-dire remplacer les séquences $[1,1]$ par $[-1,0,1]$.
\end{itemize}

\Q Ecrire une procédure \emph{powsignee(n,E,P)} qui, étant donnés un entier naturel $n$, une courbe elliptique $E$ sur un corps fini et un point $P$ sur $E$, renvoie le point $[n]P$ et le nombre total d'additions et de soustractions réalisées sur la courbe elliptique. Cette procédure doit \textbf{obligatoirement} utiliser la représentation binaire signée creuse de $n$.

\Q Tester sur de nombreux exemples. Limite de la méthode?

\exo Soit $E$ la courbe elliptique sur $\FM_q$ où $q=10^{17}+19$ est un nombre \textbf{premier} d'équation
\begin{equation*}
y^2=x^3+1
\end{equation*}
et
\begin{eqnarray*}
P & = & [72099116723710135,13462105356828521], \\
Q & = & [35311982324987694,4803038159023948].
\end{eqnarray*}
Résoudre le problème du logarithme discret
\begin{equation*}
Q=[m]P.
\end{equation*}
\textbf{\textit{Indication}}:
\begin{itemize}
\item
vous pourriez vérifier que $P$ et $Q$ sont deux points de $E$;
\item
vous pourriez vous souvenir qu'il suffit de connaître $m$ modulo $n(P)$ où $n(P)$ est l'\textbf{ordre} de $P$;
\item
vous pourriez calculer $n(P)$ en utilisant la méthode Pas de bébés-Pas de géants;
\item
vous pourriez finalement résoudre ce problème du logarithme discret sachant que si $p$ est un diviseur premier de $n(P)$ alors
\begin{equation*}
Q_p=[m_p]P_p
\end{equation*}
où
\begin{eqnarray*}
P_p & = & \left[\frac{n(P)}{p}\right]P, \\
Q_p & = & \left[\frac{n(P)}{p}\right]Q.
\end{eqnarray*}
\end{itemize}

%\Q  Question 
%\Q* Question difficile
\end{document}
