\documentclass[11pt]{amsart}
\usepackage{kbexo}
\course{N1MA9W05 -- Algo.~de la crypto.~à clé publique}
\DeclareMathOperator{\Rem}{mod}
\def\kbd#1{\texttt{#1}}
\def\pow{\^{}\hskip0pt}
\def\thepage{}

\begin{document}
\pbtitle{Examen, 19 décembre 2014 (08\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},
\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}

\noindent On rappelle la \emph{borne de Hasse}: pour toute courbe elliptique
$E/\FM_q$, on a
$$\abs{\#E(\FM_q) - (q+1)} \leq 2\sqrt{q}.$$

\exo Prouver que l'entier $9\cdot 2^{500} + 19$ est composé.

\exo Donner une preuve de primalité (par exemple $p-1$ ou méthode des courbes
elliptiques) des entiers $N$ suivants:
$$ 10^{50} + 151,\quad 
10^{101} + 3,\quad
10^{199} + 153.\quad
$$

\exo Soit $m > 0$ un entier. On cherche une puissance $q$ d'un premier $p$
et une courbe elliptique $E$ définie sur $\FM_q$ telle que $\#E(\FM_q) = m$.
\Q Dans quel intervalle faut-il chercher $q$?
\Q Trouver un premier $p$ et une courbe elliptique $E/\FM_p$ telle
que $\#E(\FM_p) = 2014$.
\Q Trouver $q$ non premier et $E/\FM_q$ telle que $\#E(\FM_q) = 2014$.


\exo Construire explicitement une implantation minimale du protocole ElGamal
(chiffrement et déchiffrement) basée sur une courbe elliptique «sure» de
cardinal $\approx 2^{200}$. On ne se préoccupera pas d'assurer l'intégrite ou
l'authenticité du message (via fonctions de hachage, etc.). Indiquer
explicitement les attaques contre lesquelles vous vous prémunissez, et pour
quelle raison.

\exo Soit $p$ un nombre premier impair et $a\in \FM_p$ un carré. On désire
calculer une racine carrée de $a$ dans $\FM_p$.
\Qqq Si $p\equiv 3\pmod{4}$, montrer que $a^{(p+1)/4}$ est une racine carrée de
$a$.
\qq Implanter l'algorithme correspondant. Quelle est sa complexité binaire ?
\Q Soit $u\in\FM_p$ tel que $D := u^2 - a$ ne soit pas un carré modulo $p$.
\qq Dans $\FM_{p^2} \simeq \FM_p[t]/(t^2-D)$, montrer que $t^p = -t$, puis que
$$(u+t)^{p+1} = u^2 - t^2 = a.$$
\qq En déduire une formule simple donnant une racine carrée de $a$.
\qq Implanter l'algorithme correspondant, en testant $u = 0,1,2,\dots$ On
pourra poser

\kbd{t = ffgen(t\pow 2 - Mod(D,p))}.

\qq Quelle est sa complexité binaire ?

\exo Soit $p = 10^{20}+39$.
\Q Calculer l'ordre de $3$ dans $\FM_p^*$ sans utiliser \kbd{znorder}.

\Q Calculer $x$ dans $\ZM/(p-1)\ZM$ tel que $3^x = 5$ dans $\FM_p$
sans utiliser \kbd{znlog}.

\Q Existe t'il $y$ tel que $5^y = 3$ dans $\FM_p$?
\end{document}
