\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, 13 décembre 2007 (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 Dans cet exercice, $N$ désigne un nombre premier et $D$ est un
entier négatif, congru à $0$ ou $1$ modulo $4$. On note $(*)$ l'équation
$U^2 - DV^2 = 4N$, où $U$ et $V$ sont entiers. La fonction
\kbd{qfbsolve(Q,N)} résoud l'équation $Q(U,V) = N$, où $Q$ est une forme
quadratique binaire, créée par \kbd{Qfb}.

\Q Rédiger un programme de résolution de $(*)$ dans le cas 
$D \equiv 0\pmod{4}$. On pourra utiliser \kbd{qfbsolve} et
\kbd{Qfb(1,0,-D/4)}.

\Q En remarquant qu'une solution de $U^2 - DV^2 = 4N$ où $U$ et $V$
sont de même parité est de la forme $(U,V) = (2x+y, y)$, écrire un
programme de résolution de $(*)$ pour $D \equiv 1\pmod{4}$.
On pourra utiliser \kbd{qfbsolve} et \kbd{Qfb(1,1,(1-D)/4)}.

\Q Donner une preuve de primalité ($p-1$ ou ECPP) des entiers $N$ suivants:
$$ 10^{50} + 151,\quad 
10^{200} + 357,\quad
10^{400} + 69 $$
Pour ECPP, tant mieux si on dispose d'une preuve complète, mais on pourra se
contenter
\begin{itemize}
\item de la suite des cardinaux des courbes à construire,

\item de la construction explicite d'une courbe de la liste,

\item d'un point d'ordre suffisant sur cette courbe.
\end{itemize}

\Q Chronométrer les différentes parties de votre programme sur un exemple
de taille raisonnable. Quelles pistes d'amélioration pourrait-on suivre ?

\exo Soit $E$ la courbe elliptique d'équation $y^2 = x^3 + 1$.
\Q Soit $p = 10^{15}+37$ (qui est premier) et on considère $E$ sur $\FM_p$
\qq Trouver un point $P$ de la forme $(11,y)$ d'ordre $p+1$ dans $E(\FM_p)$. 
\qq En déduire le cardinal $\#E(\FM_p)$.
\qq Soit $Q = [6, 92312033003029]$, 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$ se factorise facilement.}

\Q Soit maintenant $p = 10^{29}+319$.
\qq Trouver un point $P$ d'ordre $p+1$ sur $E$.
\qq Soit $Q$ un point d'abscisse $14$ (il y en a deux, choisissez-en un).
Calculer le logarithme discret de $Q$ en base $P$. 

\end{document}
