\documentclass[12pt,a4paper]{article}
\usepackage{multicol}
\usepackage[french]{babel}
\newfont{\mini}{cmssi10 scaled 480}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\euro{\mbox{\textsf{C}\kern -2.33em{\raise0.24ex\vbox{\small\it =}}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\fin{\nolinebreak \raise-0.1em\hbox{$\Box$}}
\def\stackunder#1#2{\mathrel{\mathop{#2}\limits_{#1}}}
\def\dual{ ^{\rm v}}
\def\bidual{ ^{\rm vv}}
\def\primedual{ ^{\prime \rm v}}
\def\ideal{{\cal J}}
\def\LL{{\cal L}}
\def\max{{\cal M}}
\def\quot#1#2{\mbox{\raise 0.1cm\hbox{$#1$}{\big /}\raise -0.1cm\hbox{$#2$}}}
\def\danger{{\Large \bf
    $\bigtriangleup$}\kern-0.32cm\raise0.05cm\hbox{\small
    !}\kern0.32cm\lower0.05cm\hbox{}}
%%%%%%%
\newlength{\largeurtmp}
\def\rela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.6\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.6\largeurtmp}
\def\petitrela{\settoheight{\largeurtmp}{Z}{\rm Z} \kern -0.4\largeurtmp
  \raise 0.05cm\hbox{\tiny{\it /}}\kern 0.4\largeurtmp}
\def\petitcomplex{{
    \settoheight{\largeurtmp}{$_C$}{\rm C}\kern -\largeurtmp
    \rule{0.25pt}{1.3\largeurtmp}\kern \largeurtmp}}
\def\complex{{
    \settoheight{\largeurtmp}{Q}{\rm C}\kern -0.66\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.66\largeurtmp}}
\def\ratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.75\largeurtmp
    \rule{0.25pt}{0.9\largeurtmp}\kern 0.75\largeurtmp}}
\def\petitratio{{
    \settoheight{\largeurtmp}{C}{\rm Q}\kern -0.6\largeurtmp
    \rule{0.25pt}{0.6\largeurtmp}\kern 0.6\largeurtmp}}
\newcommand{\proj}{{\rm I} \! {\rm P}}
\newcommand{\reel}{{\rm I} \! {\rm R}}
\newcommand{\Fp}{{\rm I} \! {\rm F}_p}
\newcommand{\nat}{{\rm I} \! {\rm N}}
%%%%%%%%%%%%%%%Debut de macros de fiches d'exos
%%les macros sont \exo, \qu, \quskip \squ \qusqu \qusquskip
\newcounter{exo}
\newcounter{question}
\newlength{\lng}
\newcounter{sousquestion}
\setcounter{exo}{1}
\def\exo{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}:}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\exotitre#1{

  \bigskip
  \noindent{\bf Exercice
    \Roman{exo}: #1}\addtocounter{exo}{1}\setcounter{question}{0}\nopagebreak 

  }
\def\qu{

  \addtocounter{question}{1}\arabic{question})
  \setcounter{sousquestion}{1} }
\def\quskip{

  \bigskip
  \qu}
\def\squ{

  \settowidth{\lng}{\arabic{question})
  }\hspace{\the\lng}\alph{sousquestion}) \addtocounter{sousquestion}{1}} 
\def\qusqu{\qu\nopagebreak \vskip -1\baselineskip \squ}
\def\qusquskip{\quskip\nopagebreak \vskip -1\baselineskip \squ}

%%reference pour exos,squ {\`a} placer avant la question, qu est a placer apres
\def\labelexo#1{\expandafter\edef\csname refexo#1\endcsname {\Roman{exo}}}
\def\refexo#1{\csname refexo#1\endcsname}
\def\labelqu#1{\expandafter\edef\csname refqu#1\endcsname {\arabic{question})}}
\def\refqu#1{\csname refqu#1\endcsname}
\def\labelsqu#1{\expandafter\edef\csname refsqu#1\endcsname
  {\arabic{question}\alph{sousquestion})}} 
\def\refsqu#1{\csname refsqu#1\endcsname}  

%%%%%%%%%%fin de macros fiche d'exos
%%macros taille page
\newlength{\elargir}
\setlength{\elargir}{2.5cm}
\addtolength{\leftmargin}{-\elargir}
%%\addtolength{\hoffset}{-\elargir}
\addtolength{\oddsidemargin}{-\elargir}
\addtolength{\evensidemargin}{-\elargir}
\addtolength{\elargir}{\elargir}
\addtolength{\textwidth}{\elargir}
\addtolength{\textheight}{11\baselineskip}
\topmargin=-5\baselineskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%        
\everymath={\displaystyle}
\begin{document}
\noindent{\bf Universit{\'e} de Paris 7 \hfill \framebox{\Large \bf
    \hspace{ 1cm} TP17 Courbes elliptiques.\hspace{1cm}}\hfill   agreg 2007 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
%%\columnsep 0.7cm
%%\begin{multicols}{2}
%  interface(screenwidth=120);
On pourra {\'e}tudier ces questions dans le livre de B. Perrin-Riou:
Alg{\`e}bre arithm{\'e}tique et maple. 
\section{Loi de groupe.}
Soit $k$ un corps de caract{\'e}ristique diff{\'e}rente de $2$, et
$x^3+ax^2+bx+c$ un {\'e}l{\'e}ment de $k[x]$ {\`a} racines
simples. Dans le plan affine $A=k^2$, on consid{\`e}re la ``courbe'' $C$
d'{\'e}quation $y^2=x^3+ax^2+bx+c$. On remarque que dans le compl{\'e}t{\'e}
projectif $\proj$ de $A$, la courbe\footnote{Quel est le lien entre
  ces 2 courbes?} $\bar{C}$ d'{\'e}quation
$y^2.z=x^3+ax^2z+bxz^2+cz^3$ 
rencontre  la droite de l'infini en un unique point $\Omega$, correspondant au
point {\`a} l'infini de l'axe des $y$.

Nous allons d{\'e}finir sur $\bar{C}=C\cup \{\Omega\}$
une structure de groupe  ab{\'e}lien d'origine $\Omega$. Pour $P,Q\in
\bar{C}$, notons $d$ la droite projective $(PQ)$ si $P\neq Q$, et la
tangente {\`a} $P$ en $\bar{C}$ si $P=Q$. Puisque l'intersection de
$\bar{C}$ avec $d$ a d{\'e}j{\`a} 2 points de coordonn{\'e}es  dans $k$, elle en
poss{\`e}de un ``troisi{\`e}me'' $R$ que l'on peut toujours d{\'e}finir
rigoureusement de mani{\`e}re alg{\'e}brique. (En effet un polyn{\^o}me de degr{\'e} 3 {\`a} une
variable ayant 2 racines dans $k$ a toutes ses racines dans $k$). On
consid{\`e}re alors la droite $(\Omega R)$, elle recoupe $\bar{C}$ en un
troisi{\`e}me point qui sera par d{\'e}finition $P+Q$.  

On obtient alors une loi clairement commutative, mais aussi
associative\footnote{On pourra tester ce point sur des exemples une
  fois la loi programm{\'e}e}. On remarque de plus que $\Omega+P=P$ pour
tout $P$ de $\bar{C}$. De plus  les calculs des coordonn{\'e}es de $P+Q$ en
fonction de celles de $P$ et de $Q$ sont explicites. Si $P$ a pour
coordon{\'e}es $(x,y)$, alors $-P$ a pour coordonn{\'e}es\footnote{Pourquoi?
  interpr{\'e}tation g{\'e}om{\'e}trique} $(x,-y)$

Lorsque $n$ est un entier relatif, on peut calculer $n.P$ en
$O(\log(n))$  additions.\footnote{On pourra justifier ce point.}

\section{La m{\'e}thode de Lenstra}
On peut par exemple utiliser cette loi pour tenter de trouver un
facteur non trivial d'un entier. Par exemple au lieu de travailler
dans $k=\rela/p\rela$, o{\`u} $p$ est un premier impair, on peut
travailler dans $\rela/N.\rela$, et dans la
proc{\'e}dure de calcul de $n.P$ tester\footnote{Si l'on travaille en
  affine cela revient {\`a} regardre si les divisions que l'on doit
faire sont licites en calculant un pgcd avec $N$} {\`a} chaque addition si un des points
est {\`a} l'infini\footnote{Les points {\'e}tant sur la courbe, cela revient {\`a}
tester si un point vaut $\Omega$ dans $\proj(\rela/m\rela)$ o{\`u} $m$
divise $N$} modulo un diviseur de $N$. Si l'on arrive {\`a} une
impossibilit{\'e}, on a obtenu un diviseur non trivial de $N$.

Par exemple, avec $N$ du type
\code{nextprime(20000)*nextprime(40000);}, et $n$ un ppcm d'entiers
petits, $P=(2,1)$. On cherche alors des courbes $C$ contenant $P$ telles
que le calcul de $n.P$ donne un facteur non trivial de $N$. Prenons
$C$ du type $y^2=x^3+bx+c$, pour $b\in\{1,\dots,50\}$ on trouve
rapidement les $c$ tels que $P\in C$, et pour ces valeurs de $C$ on
calcule $n.P$. On pourra essayer d'autres exemples, et estimer le
nombres d'additions effectue{\'e}es sur la courbe elliptique pour briser
$N$.

\section{Suggestions de d{\'e}veloppements}
\qu Le candidat pourra justifier les notes      de bas de page.
\qusqu Cr{\'e}er une proc{\'e}dure point r{\'e}siduel recevant $2$ points de
$\bar{C}$ et retournant le "troisi{\`e}me" point d'intersection d{\'e}crit
dans l'{\'e}nonc{\'e}.
\squ Programmer l'addition sur $\bar{C}$
\qu Cr{\'e}er une proc{\'e}dure de multiplacation par un entier $n$ en $O(\log
n)$ additions. On pourra le faire d'abord avec l'addition dans $\rela$
puis sur la courbe elliptique.
\qu Cr{\'e}er une proc{\'e}dure pour tester s'il existe un diviseur $m$ de $N$
tel que le point de coordonn{\'e}es
projectives $(x,y,z)$ soit {\'e}gal {\`a} $\Omega$ dans
$\proj(\rela/m\rela)$. Sans factoriser $N$ bien sur!
\qu Modifier les op{\'e}rations pr{\'e}c{\'e}dentes pour impl{\'e}menter la m{\'e}thode de
Lenstra.
\qu Quelles m{\'e}thodes utilise votre logiciel?
\section{V{\'e}rifications, manipulation}
Les op{\'e}rations sur les courbes elliptiques sont d{\'e}ja impl{\'e}ment{\'e}es
dans le logiciel libre pari aussi appel{\'e} gp. La courbe $E$ d'{\'e}quation
$y^2+a.yx+cy=x^3+b.x^2+dx+e$ se definit par le vecteur:
\code{E=[a,b,c,d,e]}, le point P est not{\'e} en affine \code{P=[2,1]} et
l'on peut faire \code{elladd(E,P,P)} ou ellpow(E,P,10).
Par exemple, sous  pari-gp:
\begin{verbatim}
? P=[2,1]
? E=[0,1,0,2,-15]
? elladd(E,P,P)
? ellpow(E,P,10)
? N=nextprime(100000)*nextprime(10000)
? P=Mod([2,1],N)
? ellpow(E,P,1000)
? ellpow(E,P,100000000000000000)
  ***   impossible inverse modulo: Mod(10007, 1000730021).
?n=232792560;for(b=1,50,ellpow([0,0,0,b,-7-2*b],P,n))
\end{verbatim}
%# egalite de 2vecteurs a facteur pres:
% egal:=proc(P,Q);
% a:=expand(P[1]*Q[2]-P[2]*Q[1]);
% b:=expand(P[3]*Q[2]-P[2]*Q[3]);
% c:=expand(P[1]*Q[3]-P[3]*Q[1]);
% if [a,b,c]=[0,0,0] then true; else false; fi;
%end proc;
%#On cree une procedure simplifier que l'on pourra modifier ensuite:
%simplifier:=proc(R)
%d:=igcd(R[1],R[2],R[3]);
%R/d;end proc;
% #C y^2=x^3+ax^2+bx+c
%pointresiduel:=proc(a,b,c,P,Q)
%C:=-y^2*z+x^3+a*x^2*z+b*x*z^2+c*z^3;
%if egal(P,Q) then
%#la tangente est P+tQQ
%QQ:=[subs(x=P[1],y=P[2],z=P[3],diff(C,y)),subs(x=P[1],y=P[2],z=P[3],-diff(C,x)),0];
%M:=expand(P+t*QQ);d:=subs(x=M[1],y=M[2],z=M[3],C);
%sol:=simplify(d/t^2);
%%#ce vecteur doit etre non nul.
%if egal(QQ,[0,1,0]) then R:=QQ; else R:=expand(-coeff(sol,t,1)*P+coeff(sol,t,0)*QQ);fi;
%else
%#On parametre (PQ) par P+tQ, 0 et l'infini sont solutions.
%M:=expand(P+t*Q);d:=subs(x=M[1],y=M[2],z=M[3],C);
%#sol doit etre un poly de degre 1 puisque 0 et l'infini sont solutions.
%sol:=simplify(d/t);
%#ce vecteur doit etre non nul.
%R:=expand(-coeff(sol,t,1)*P+coeff(sol,t,0)*Q);
%fi;
%simplifier(R);
%end proc;
%#exemple:
%P:=[0,0,1];Q:=[1,1,1];omega:=[0,1,0];
%#verification egal:
% if egal(P,Q) then print(eg) else  print(noneg) fi;
% if egal(P,P) then print(eg) else  print(noneg) fi;
% pointresiduel(1,-1,0,P,Q),pointresiduel(1,-1,0,P,omega),pointresiduel(1,-1,0,P,omega);
%#addition:
%plus:=proc(a,b,c,P,Q)
%R:=pointresiduel(a,b,c,P,Q);
%R[2]:=-R[2];
%R;
%end proc;
%plus(1,-1,0,omega,omega),plus(1,-1,0,P,omega),plus(1,-1,0,P,P);R:=plus(1,-1,0,P,Q);
%#On programme la mult par n en O(log n) additions.
%nplus:=proc(a,b,c,P,n)
%Y:=[0,1,0];X:=P;m:=n;
%while m>1 do
%  if type(m,even) then  X:=plus(a,b,c,X,X);m:=m/2;
%  else Y:=plus(a,b,c,X,Y);X:=plus(a,b,c,X,X);m:=(m-1)/2;
%  fi;end do;
%  plus(a,b,c,X,Y);end proc;
%#P est d'ordre 2, Q d'ordre 3, P+Q d'ordre 6 
% nplus(1,-1,0,P,2),nplus(1,-1,0,Q,2),nplus(1,-1,0,Q,3),nplus(1,-1,0,R,3),nplus(1,-1,0,R,2),nplus(1,-1,0,R,6);
% 
%#Pb de factorisation.
%egalomega:=proc(P,N)
% Q:=[0,1,0];
% a:=expand(P[1]*Q[2]-P[2]*Q[1]);
% b:=expand(P[3]*Q[2]-P[2]*Q[3]);
% c:=expand(P[1]*Q[3]-P[3]*Q[1]);
% g:=igcd(a,b,c,N);
% if g<>1 and g<>N  then print("diviseur",g):true; else false; fi;
%end proc;
%#On redefinit simplifier pour travailler modulo N
%simplifier:=proc(R)
%d:=igcd(R[1],R[2],R[3],N);
% if d<>1 and d<>N then print("diviseur",d); break;
%else  R mod N;fi;end proc;
%
%#On redefinit plus pour qu'il s'arrete si l'on obtient
%#omega modulo un diviseur strict de N.
%plus:=proc(a,b,c,P,Q)
%R:=pointresiduel(a,b,c,P,Q);
%R[2]:=-R[2];
%if egalomega(R,N) then break; fi;
%R;
%end proc;
%#factorisation d'un entier via les courbes elliptiques
%n:=ilcm(seq(i,i=1..19));
%#On cherche c tel que (2,1) soit sur y^2=x^3+bx+c
%P:=[2,1,1];N:=nextprime(20000)*nextprime(40000);
%for a from 1 to 3 do for b from 1 to 20
%do nplus(a,b,P[2]^2-P[1]^3-a*P[1]^2-b*P[1],P,n) od:od:
%print("trouve en a b"),a,b;
%N:=nextprime(1234567)*nextprime(7654321);n:=ilcm(seq(i,i=1..50));
%for a from 1 to 3 do for b from 1 to 20
%do nplus(a,b,P[2]^2-P[1]^3-a*P[1]^2-b*P[1],P,n) od:od:
%print("trouve en a b"),a,b;

    
%%\newpage
%%\end{multicols}

\end{document}

