\documentclass[10pt,a4paper]{article}

\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsmath}
\usepackage{fullpage}
\usepackage{supertabular}
\usepackage[french]{babel}

\DeclareMathSymbol{\gena}{\mathord}{letters}{"3C}
\DeclareMathSymbol{\genb}{\mathord}{letters}{"3E}
\newcommand{\scal}[2]{\gena{#1},{#2}\genb}

\newcommand{\ra}{\rightarrow}
\newcommand{\trib}{\mathcal{M}}
\newcommand{\Rr}{\mathbf{R}}
\newcommand{\Nn}{\mathbf{N}}
\newcommand{\Cc}{\mathbf{C}}
\newcommand{\Zz}{\mathbf{Z}}
\newcommand{\Qq}{\mathbf{Q}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\tq}{\,\mid\,}
\newcommand{\eps}{\varepsilon}
\newcommand{\Parts}{\mathcal{P}}
\newcommand{\mods}[1]{\, (\mathrm{mod}\, {#1})}
\newcommand{\norm}[1]{\vert\vert{#1}\vert\vert}
\def\stacksum#1#2{{\stackrel{{\scriptstyle #1}}
{{\scriptstyle #2}}}}
\newcommand{\Cic}{C_c^{\infty}}
\newcommand{\ppartial}{\tilde{\partial}}
\newcommand{\indic}[1]{[\underline{Indication}~:\ {#1}]}

\newcommand{\implique}{\Rightarrow}
\newcommand{\ssi}{\Leftrightarrow}

\newcommand{\bareme}[1]{\marginpar{(\small{\textsf{{#1}}})}}
\newcommand{\baremeg}[1]{\marginpar{\framebox{\textsf{{#1}}}}}



\newcounter{exercices}
\newcounter{etape}

\newenvironment{exo}{\par\setcounter{etape}{0}\stepcounter{exercices}
\medskip\textbf{Exercice {\arabic{exercices}}.}\ }

\newcommand{\etap}{\stepcounter{etape}(\arabic{etape})\ }

\begin{document}

\selectlanguage{french}

\begin{flushleft}
\textbf{Université Bordeaux I -- 2009/2010}\hfill
\textbf{Master 1 Cryptologie et Sécurité Informatique}
\par
\textbf{Courbes elliptiques}\hfill\textbf{K. Belabas - F. Pazuki}
\end{flushleft}

\bigskip
\bigskip

\begin{center}
\textbf{TD 2}
\end{center}

\par
\bigskip

%% \noindent
%% \textsf{\underline{Barême indicatif} : $???$}

Une courbe elliptique $E$ est une équation
\begin{equation*}
y^2+a_1xy+a_3y=x^3+a_2x^2+a_4x+a_6
\end{equation*}
où les coefficients $(a_i)_{i\in\left\{1,\cdots,4,6\right\}}$ sont des éléments d'un corps $\mathbb{K}$. En abrégé,
\begin{equation*}
E=[a_1,a_2,a_3,a_4,a_6].
\end{equation*}

%\begin{exo}
%L'objectif de cet exercice est d'appliquer la méthode d'exponentiation binaire sur une courbe elliptique $E$ définie sur $\mathbb{C}$.  
%\begin{enumerate}
%\item 
%Écrire une procédure permettant de calculer $n.P$ si $n$ est un entier naturel et $P$ est un point de $E$ en vous inspirant du TD1.
%\item
%Si $E: y^2=x^3+256$ alors vérifier que $P=(0,16)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente.
%\item
%Si $E: y^2=x^3+x/4$ alors vérifier que $P=(1/2,1/2)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente.
%\item
%Si $E: y^2=x^3-43x+166$ alors vérifier que $P=(3,8)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente.
%\end{enumerate}
%\end{exo}

\begin{exo}
Soit $E$ une courbe elliptique d'{e}finie sur un corps $\mathbb{K}$. L'objectif de cet exercice est de calculer, via l'algorithme de la fenêtre flexible, $[n]P$ étant donnés un entier naturel $n$ et un point $P$ de $E$.
\begin{enumerate}
\item
Écrire une procédure qui, étant donné un entier naturel non-nul $k$ et un point $P$ de $E$, calcule le vecteur
\begin{equation*}
\left(P,[2]P,[4]P,\cdots,[2^k]P\right).
\end{equation*}
Appelez-là \textit{powinit(E,P,k)}.
\item
Écrire une procédure qui, étant donné un entier naturel $n$ et un point $P$ de $E$, calcule le point $[n]P$. Appelez-là \textit{flexpow(E,P,n)}. Conseil: écrire
\begin{equation*}
n=2^v(2^kq+r)
\end{equation*}
où $0\leqslant r<2^k$ est un entier naturel impair, $q$ et $v$ sont deux entiers naturels.
\item
Tester sur de nombreux exemples de courbes elliptiques sur des corps finis pour des valeurs de $k$ différentes et comparer avec la fonction \textit{ellpow}. Conseil: Écrire une procédure qui, étant donnée une courbe elliptique $E$ sur le corps fini $\mathbb{F}_q$ avec $q=p^m$ renvoie un point aléatoire sur $E$ i.e. un élément aléatoire de $E(\mathbb{F}_q)$. Appelez-là \textit{ellrand(E,p,m)}.
\item
Si $E$ est la courbe elliptique rationnelle, i.e. sur $\mathbb{Q}$, définie par $y^2=x^3+256$ alors calculer son discriminant à l'aide de gp puis vérifier que $P=(0,16)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente. Comparer avec la fonction \textit{ellorder}.
\item
Si $E$ est la courbe elliptique rationnelle définie par $y^2=x^3+x/4$ alors calculer son discriminant à l'aide de gp puis vérifier que $P=(1/2,1/2)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente. Comparer avec la fonction \textit{ellorder}.
\item
Si $E$ est la courbe elliptique rationnelle définie par $y^2=x^3-43x+166$ alors calculer son discriminant à l'aide de gp puis vérifier que $P=(3,8)$ est bien sur la courbe elliptique et est un point de torsion. Calculer son ordre à l'aide de la procédure précédente. Comparer avec la fonction \textit{ellorder}.
\end{enumerate}
\end{exo}

\begin{exo}
L'objectif de cet exercice est de calculer quelques logarithmes discrets via la méthode $\rho$ de Pollard. Soit $E$ une courbe elliptique sur $\mathbb{F}_q$ avec $q=p^m$. Soient $P$ et $Q$ dans $E(\mathbb{F}_q)$ avec
\begin{equation*}
Q\in\langle P\rangle:=\left\{[k]P,k\in\mathbb{Z}\right\}.
\end{equation*}
On cherche un entier naturel $n$ (modulo l'ordre de $P$\dots) satisfaisant $Q=[n]P$, i.e. on cherche $\log_P{(Q)}$. Soit $\langle P\rangle=G_1\amalg G_2\amalg G_3$ une partition de $\langle P\rangle$ en trois sous-ensembles de taille equivalente. On définit une marche aléatoire sur $\langle P\rangle$ par $w_0=P$ et
\begin{equation*}
w_{i+1}=\Phi(w_i)=\begin{cases}
w_i+Q & \text{si $w_i\in G_1$,} \\
[2]w_i & \text{si $w_i\in G_2$,} \\
w_i+P & \text{sinon}
\end{cases}
\end{equation*}
pour tout entier naturel $i$.
\begin{enumerate}
\item
Imaginer une facon de partitionner $\langle P\rangle$.
\item
Montrer que si cette marche aléatoire présente une collision alors vous êtes capables de trouver $\log_P{(Q)}$.
\item
Montrer qu'il existe un entier naturel $i$ grand satisfaisant $w_i=w_{2i}$. Écrire une procédure qui, étant donnés $P$ et $Q$ renvoie $n$. Appelez-là \textit{pollard(E,P,Q,p,m)}. Discutez ses avantages et ses inconvénients. 
\item
Écrire une première amélioration sachant qu'il existe un entier naturel $i$ satisfaisant $w_i=w_{\ell(i)-1}$ où $\ell(i)$ est la plus grande puissance de $2$ inférieure à $i$ ie $\ell(i):=2^{E(\log{(i)})}$ où $E(x)$ est la partie entière de $x$. Appelez-là \textit{pollard2(E,P,Q,p,m)}. Discutez ses avantages et ses inconvénients.
\item
Écrire une deuxième amélioration sachant qu'il existe un entier naturel $i$ satisfaisant $w_i=w_{\ell(i)-1}$ et $3\ell(i)/2\leqslant i\leqslant 2i$. Appelez-là \textit{pollard3(E,P,Q,p,m)}. Discutez ses avantages et ses inconvénients.
\item
Comparer ces diverses procédures sur l'exemple suivant: $E$ est la courbe elliptique définie sur $\mathbb{F}_{173}$ par
\begin{equation*}
y^2=x^3+146x+33
\end{equation*}
et $P=(168,133)$ et $Q=(147,74)$.
\item
Tester sur vos exemples préférés.
\end{enumerate}
\end{exo}



\begin{exo}
L'objectif de cet exercice est de calculer quelques logarithmes discrets via la méthode Pas de bébés-Pas de géants. Soient $E$ une courbe elliptique sur un corps $\mathbb{K}$ et $P$ un point d'ordre $\ell$. Tout repose sur le fait que si $s=E(\sqrt{l})+1$ alors il existe des entiers naturels $U$ et $V$ compris entre $0$ et $s$ tels que
\begin{equation*}
n=U+Vs.
\end{equation*} 
\begin{enumerate}
\item
Étant donnés une courbe elliptique, $Q\in\langle P\rangle$ sur celle-ci et deux réels $i_{min}$ et $i_{max}$, écrire une procédure déterminant un entier relatif $i$ satisfaisant $i.P=Q$ et $i_{min}\leqslant i\leqslant i_{max}$. Appelez-là \textit{babygiant(E,P,Q,min,max)}.
\item
En déduire une procédure déterminant l'ordre d'un point connaissant un encadrement d'un multiple de l'ordre.
\item
En déduire une procédure déterminant l'ordre d'un point sur une courbe elliptique sur un corps fini.
\item
Appliquer la procédure suivante à la courbe elliptique définie sur $\mathbb{F}_{173}$ par
\begin{equation*}
y^2=x^3+146x+33
\end{equation*}
et aux points $P=(168,133)$ et $Q=(147,74)$.
\end{enumerate}
\end{exo}


\begin{exo}
L'objectif de cet exercice est d'avoir en stock des procédures permettant de calculer l'ordre d'un point sur une courbe elliptique $E$ sur un corps $\mathbb{K}$.
\begin{enumerate}
\item
Écrire une procédure déterminant l'ordre d'un point connaissant la factorisation d'un multiple de l'ordre.
\item
En déduire une procédure déterminant l'ordre d'un point connaissant un multiple de l'ordre.
\item
Appliquer les procédures précédentes à la courbe elliptique définie sur $\mathbb{F}_{173}$ par
\begin{equation*}
y^2=x^3+146x+33
\end{equation*}
et aux points $P=(168,133)$ et $Q=(147,74)$.
\end{enumerate}
\end{exo}

\begin{exo}
L'objectif de cet exercice est de tracer graphiquement les trajectoires des
itérés de points choisis aléatoirement sur une courbe elliptique définie sur
$\mathbb{F}_p$ où $p$ est un nombre premier (101, 2003, \dots).
\begin{enumerate}
\item
Écrire une procédure représentant graphiquement une courbe elliptique sur $\mathbb{F}_p$ puis représentant graphiquement l'arc
\begin{equation*}
P\rightarrow [2]P\rightarrow [3]P\rightarrow\cdots\rightarrow [n]P
\end{equation*}
où $n$ est bien choisi et $P$ est un point aléatoire sur la courbe elliptique. Conseil: vous pourriez representer $\mathbb{F}_p$ sur l'axe des abscisses par $\left\{0,1,\cdots,p-1\right\}$ et sur l'axe des ordonnées par $\left\{-(p-1)/2,\cdots,(p-1)/2\right\}$.
\item
Tester sur quelques courbes elliptiques et sur plusieurs points pour voir si des choses intéressantes se passent.
\item
Changez éventuellement de point de vue, i.e. fixer une courbe elliptique $E$ sur $\mathbb{Q}$ et un point $P$ à coefficients dans $\mathbb{Z}$ sur $E$ d'ordre infini. Pour chaque nombre premier $p$, représenter graphiquement la courbe elliptique $\overline{E}_p$ ie la réduction de la courbe elliptique $E$ sur $\mathbb{F}_p$ ainsi que la trajectoire des itérés de $\overline{P}_p$ ie la réduction modulo $p$ de $P$. Prendre $p$ de plus en plus grand. Se passent-il des choses intéressantes?   
\end{enumerate} 
\end{exo}

\begin{exo}
Soit $E$ une courbe elliptique définie sur $\mathbb{Q}$ de discriminant $\Delta$ sans facteurs carrés et à coefficients dans $\mathbb{Z}$. Pour tout nombre premier $p$ ne divisant pas $\Delta$, on note $\overline{E}_p$ la réduction de $E$ modulo $p$ puis $\overline{E}_p(\mathbb{F}_p)$ le groupe des points $\mathbb{F}_p$-rationnels de $\overline{E}_p$. Vous savez désormais que $\overline{E}_p(\mathbb{F}_p)$ est un groupe fini de cardinal $p+1-t_p$, où $t_p$ est la trace du Frobenius, isomorphe à 
\begin{equation*}
\mathbb{Z}\left/d_{1,p}\mathbb{Z}\right.\times\mathbb{Z}\left/d_{2,p}\mathbb{Z}\right.
\end{equation*}
où $d_{1,p}\mid d_{2,p}$. L'objectif de cet exercice est de deviner numériquement le comportement asymptotique de
\begin{equation*}
N_E(X)=\left\vert\left\{p\leqslant X, p\in\mathcal{P}, p\nmid\Delta, \overline{E}_p(\mathbb{F}_p) \text{ cyclique}\right\}\right\vert
\end{equation*} 
lorsque $X\to+\infty$. Vous avez toutes les cartes en main. Pour tester la cyclicité de $\overline{E}_p(\mathbb{F}_p)$, vous pourriez tirer au hasard un point sur $\overline{E}_p$ puis calculer son ordre et le comparer avec l'ordre de $\overline{E}_p(\mathbb{F}_p)$ par exemple. Essayer de trouver une application cryptographique à ce résultat.
\end{exo}

\begin{exo}
L'objectif de cet exercice est de vérifier la loi de Sato-Tate prouvée par Taylor. Si $E$ est une courbe elliptique sur $\mathbb{Q}$ de discriminant sans facteurs carrés et à coefficients dans $\mathbb{Z}$ et $p$ est un nombre premier alors vous savez qu'il est possible d'écrire la trace du Frobénius sous la forme
\begin{equation*}
t_p=2\sqrt{p}\cos\left(\theta_p\right)
\end{equation*}
où $0\leqslant\theta_p\leqslant\pi$. Essayer de déterminer le comportement asymptotique de
\begin{equation*}
\text{ST}_E(X)=\left\vert\left\{p\leqslant X, p\in\mathcal{P},\alpha\leqslant\theta_p\leqslant\beta\right\}\right\vert
\end{equation*}
où $0\leqslant\alpha<\beta\leqslant\pi$.
\end{exo}

\begin{exo}
Soit $E$ la courbe elliptique sur $\mathbb{Q}$ définie par
\begin{equation*}
y^2+y=x^3-7x+6.
\end{equation*}
\begin{enumerate}
\item
Quel est le discriminant de cette courbe?
\item
Trouver le groupe de torsion de cette courbe.
\item
On se propose de déterminer quelques points rationnels sur cette courbe. Si $(x,y)$ est un point réel de la courbe alors montrer à l'aide de gp que $x\geqslant -3$. En déduire une procédure renvoyant une liste de points rationnels sur la courbe à l'aide de la commande \textit{ellordinate}.
\end{enumerate}
\end{exo}

%\begin{exo}
%Soit $E$ la courbe elliptique sur $\mathbb{Q}$ d'équation
%\begin{equation*}
%y^2+2xy=x^3+x^2-2x
%\end{equation*}
%La fonction $L$ de $E$ notée $L(E,s)$ est définie sur $\Re{(s)}>3/2$ par le produit Eulerien absolument convergeant
%\begin{equation*}
%L(E,s):=\prod_{\substack{p\in\mathcal{P} \\
%p\nmid N}}\left(1-\frac{a_p}{p^s}+\frac{1}{p^{2s-1}}\right)^{-1}\prod_{\substack{p\in\mathcal{P} \\
%p\mid N}}\left(1-\frac{a_p}{p^s}\right)^{-1}
%\end{equation*}
%où $N$ est le conducteur de $E$, $\mathcal{P}$ désigne l'ensemble des nombres premiers et
%\begin{equation}\label{eq_a_p}
%\forall p\in\mathcal{P},\quad a_p:=p+1-\left\vert\overline{E}(\mathbb{F}_p)\right\vert.
%\end{equation}
%$L(E,s)$ admet un prolongement au plan complexe et satisfait une équation fonctionnelle de la forme
%\begin{equation*}
%L(E,s)\approx \omega_E L(E,1-s)
%\end{equation*}
%où $\omega_E=\pm 1$ (travaux de Wiles, Taylor, Diamond,\dots). L'objectif de cette exercice est de mettre l'accent sur le fait que cette fonction $L$ encode des informations sur la courbe elliptique et plus précisément sur le groupe de Mordell-Weil $E(\mathbb{Q})$ de $E$. L'ordre d'annulation en $s=1$ de la fonction $L$ est conjecturalement\footnote{Version faible de la conjecture de Birch et de Swinnerton-Dyer} le rang de $E(\mathbb{Q})$.
%\begin{enumerate}
%\item
%Trouver le discriminant de cette courbe.
%\item
%Montrer que $(0,0)$ est sur la courbe et est un point de torsion d'ordre 2.
%\item
%Trouver le groupe de torsion $E(\mathbb{Q})_{\text{tors}}$ de $E$.
%\item
%Déterminer une $\mathbb{Z}$-base de la partie libre du groupe $E(\mathbb{Q})$.
%\item
%Calculer la valeur spéciale de la fonction $L$ de $E$ ie $L(E,1)$.
%\item
%Trouver le signe de l'équation fonctionnelle satisfaite par $L(E,s)$. Est-ce en accord avec la parité du rang du groupe $E(\mathbb{Q})$?
%\item
%Vérifier la conjecture\footnote{Version forte de la conjecture de Birch et de Swinnerton-Dyer.} suivante à l'aide de gp
%\begin{equation*}
%L(E,1)\left(\frac{\omega_1(E)c_E}{\left\vert E(\mathbb{Q})_{\text{tors}}\right\vert^2}\right)^{-1}\in\mathbb{N}^2
%\end{equation*}
%où $\omega_1(E)$ est la période réelle de $E$, $c_E$ est le produit des nombres de Tamagawa.
%\end{enumerate}
%\end{exo}

\end{document}
