\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} TP8 Courbes elliptiques.\hspace{1cm}}\hfill   agreg 2010 (F.Han)}\\
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\def\code#1{{\tt #1}}
%% 
\columnsep 0.7cm
\begin{multicols}{2}
\exotitre{quelques fonctions graphiques}
(But:  pratique minimale de  fonctions graphiques. Ex: D\'essiner plusieurs objets
g\'eom\'etriques simultan\'ement, couleurs diff\'erentes, courbes param\'etr\'ees,
implicites...)
\qu Cr\'eer une fonction: $M:t \mapsto (\frac{\cos
  t}{\sin^3t},\frac{\sin t}{\sin^3t})$
% M:=t->(cos(t)/sin(t)^3,sin(t)/sin(t)^3);
\qusqu En mode g\'eom\'etrie, dessiner le point $M(\pi/2)$
\squ En utilisant \code{plotparam},d\'essiner la courbe $C_1:t\mapsto M(t)$.
% !s!<g>
% C1:=plotparam(M(t),t=0..Pi);
\squ Prendre des \'el\'ements $t_1$ et $t_2$ de $]0..\pi[$ et dessiner
$M(t_1),M(t_2),M(-t_1-t_2)$. Afficher ces points avec une grosse croix en taille
un peu plus grande. (On peut donner une option pour chaque point ou bien definir
la meme option globalement. etudier \code{couleur} ou \code{affichage}. On peut
aussi dessiner un point \`a la souris pour connaitre la syntaxe de ces options.)
% t1:=element(0..Pi,0.7);
% t2:=element(0..Pi,0.6);
% couleur(point_width_2+point_etoile);
% M1:=point(M(t1));M2:=point(M(t2));M3:=point(M(-t1-t2));
% droite(M1,M2,affichage=blue);
%!s!
\squ Dessiner la droite $M(t1),M(t2)$ en bleu.
\qu On consid\`ere la courbe $C_2: x^3-3x.y-1=0$
\squ Cr\'eer la fonction $f(x,y,z)=x^3-3x.y.z-z^3$, et repr\'esenter les courbes
planes $f(x,y,1)=0$ et $f(x,1,z)=0$. Ajuster le pas pour que les dessins aient
l'air bien lisse. Expliquer le comportement \`a l'infini de
$C_2$.
% f:=(x,y,z)->x^3-3*x*y*z-z^3;
% C2:=implicitplot(f(x,y,1),x,y);
% !s!<c>
% Pour ajuster le pas d'un trace implicit on utilise xstep et ystep
%pour abscisse et ordonnee, quels que soient les noms de variables.
%!s!
% C2Z:=implicitplot(f(x,1,z),x,z,xstep=0.01,ystep=0.01);
%
\exo
\qu Si vous \^etes en mode maple, etudier la priorit\'e de \code{mod}. Par exemple:
\code{3+5 mod 2;}. Quelle instruction faut il pour avoir un reste de valeur
absolue minimale.
%3+5 mod 2; # mod est prioritaire
\qu Etudier l'intruction \verb/quo(t^2+1,t)/. Qu'a t'il fait? Comment obtenir le
polyn\^ome quotient?
% quo(t^2+1,t);#fait la div selon x
% quo(t^2+1,t,t);#fait bien le quotient selon la div selon t
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% !s!<c>
%---------------------------------------------------------------------------------
% Mini texte Courbes elliptiques
%---------------------------------------------------------------------------------
% !s!
\exotitre{Mini texte courbes elliptiques}
On pourra \'etudier ces questions dans le livre de B. Perrin-Riou:
Alg\`ebre arithm\'etique et maple. 
\section{Loi de groupe.}
Soit $k$ un corps de caract\'eristique diff\'erente de $2$, et
$x^3+ax^2+bx+c$ un \'el\'ement de $k[x]$ \`a racines
simples. Dans le plan affine $A=k^2$, on consid\`ere la ``courbe'' $C$
d'\'equation $y^2=x^3+ax^2+bx+c$. On remarque que dans le compl\'et\'e
projectif $\proj$ de $A$, la courbe\footnote{Quel est le lien entre
  ces 2 courbes?} $\bar{C}$ d'\'equation
$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\'efinir sur $\bar{C}=C\cup \{\Omega\}$
une structure de groupe  ab\'elien 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\'ej\`a 2 points de coordonn\'ees  dans $k$, elle en
poss\`ede un ``troisi\`eme'' $R$ que l'on peut toujours d\'efinir
rigoureusement de mani\`ere alg\'ebrique. (En effet un polyn\^ome de degr\'e 3 \`a une
variable ayant 2 racines dans $k$ a toutes ses racines dans $k$). On
consid\`ere alors la droite $(\Omega R)$, elle recoupe $\bar{C}$ en un
troisi\`eme point qui sera par d\'efinition $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\'ee}. On remarque de plus que $\Omega+P=P$ pour
tout $P$ de $\bar{C}$. De plus  les calculs des coordonn\'ees de $P+Q$ en
fonction de celles de $P$ et de $Q$ sont explicites. Si $P$ a pour
coordon\'ees $(x,y)$, alors $-P$ a pour coordonn\'ees\footnote{Pourquoi?
  interpr\'etation g\'eom\'etrique} $(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\'ethode 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\'edure de calcul de $n.P$ tester\footnote{Si l'on travaille en
  affine cela revient \`a regarder 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 \'etant 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
\linebreak\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\'ees sur la courbe elliptique pour briser
$N$.

\section{Suggestions de d\'eveloppements}
\qu Le candidat pourra justifier les notes      de bas de page.
\qu Illustrer graphiquement l'interpr\'etation g\'eom\'etrique du point $\Omega$ via
des  dessins dans diff\'erents rep\`eres.
\qusqu Cr\'eer une proc\'edure point r\'esiduel recevant $2$ points de
$\bar{C}$ et retournant le "troisi\`eme" point d'intersection d\'ecrit
dans l'\'enonc\'e.
\squ Programmer l'addition sur $\bar{C}$
\qu Cr\'eer une proc\'edure de multiplication 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\'eer une proc\'edure pour tester s'il existe un diviseur $m$ de $N$
tel que le point de coordonn\'ees
projectives $(x,y,z)$ soit \'egal \`a $\Omega$ dans
$\proj_2(\rela/m\rela)$. Elle pourrait retourner 1 si c'est different de
$\Omega$, ou le diviseur $m$ sinon. Sans factoriser $N$ bien sur!
\qu Modifier les op\'erations pr\'ec\'edentes pour impl\'ementer la m\'ethode de
Lenstra.
\qu Quelles m\'ethodes utilise votre logiciel pour factoriser un entier? (Pour
xcas on \'etudiera la documentation de pari-gp disponible dans le menu aide, car
il me semble que xcas utilise la fonction de pari s'il le peut, sinon c'est
probablement la m\'ethode de pollar. (Cf le fichier /usr/share/giac/src/ifactor.cc).
% !s!<c>
%Etudier la documentation de factorint dans l'aide de pari-gp: Il combine
%plusieurs methodes, dont celle de Lenstra: ECM
%!s!
\section{V\'erifications, manipulation}
Les op\'erations sur les courbes elliptiques sont d\'eja impl\'ement\'ees
dans le logiciel libre pari aussi appel\'e gp. La courbe $E$ d'\'equation
$y^2+a.yx+cy=x^3+b.x^2+dx+e$ se definit par le vecteur:
\code{[a,b,c,d,e]}, le point P est not\'e en affine \code{[2,1]} et
l'on peut faire \code{elladd(E,P,P)} ou ellpow(E,P,10). Le logiciel xcas peut utiliser ces
fonctions apr\`es avoir effectue: \code{pari();} On peut par exemple faire sous xcas:
\code{P:=[1,2];} puis  \code{E:=[0,1,0,2,-15];} puis \verb/pari_ellpow(E,P,10);/ 

xcas peut fournir aussi des objets modulaire, par exemple si $N$ vaut $1000730021$, on
voudrait faire cela modulo $N$. Il suffit que le point $P$ soit un objet modulaire sous
xcas. En mode xcas: \verb/P:=[1,2]% N;/ puis \verb/pari_ellpow(E,P,10);/.
Par exemple  \verb/ellpow(E,P,10^20)/ prouve que N n'est pas premier. Pour pouvoir lire le
message d'erreur, il vallait mieux lancer xcas depuis un terminal, c'est la qu'il
apparait:

`` ***   impossible inverse modulo: Mod(553216596, 1000730021).
*** ellpow: impossible inverse modulo: Mod(553216596, 1000730021).''

En mode maple, c'est plus d\'elicat de cr\'eer un objet modulaire. Le plus simple est de
passer temporairement en mode xcas:
\begin{verbatim}
maple_mode(0);
P:=[1,2] % N;
maple_mode(1);
\end{verbatim}
ou bien d'utiliser la fonction\footnote{non document\'ee} \code{makemod}, par exemple:
\code{P:=[1,2]*makemod(1,N);}
%% Par exemple,  sous le logiciel 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,100000000000000000000)
%%   ***   impossible inverse modulo: Mod(10007, 1000730021).
%% ?n=232792560;for(b=1,50,ellpow([0,0,0,b,-7-2*b],P,n))
%%\end{verbatim}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
% !s!<c>
% egalite de 2 vecteurs a facteur pres:
%!s!
% !s!<m>
% 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;
%!s!
%!s!<c>
%On prend un courbe  C d'equation: y^2=x^3+ax^2+bx+c
%!s!
%!s!<p>
% pointresiduel:=proc(a,b,c,P,Q)
%local d,C,QQ,M,sol,R;
% 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 sauf si P est omega. Autrement dit, QQ est le point
%//d'intersection de la tangente avec la droite de l'infini, ie c'est le vecteur
%//directeur. Sauf lorsque la tangente est la droite de l'infini ie QQ=omega
%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:=normal(P+t*QQ);d:=subs(x=M[1],y=M[2],z=M[3],C);
%//on prefere quo a simpifier d/t^2, car lorsqu'on travaillera modulo N
%//d ne sera pas forcement divisible par t^2, il ne le serait que modulo N.
%//Attention a bien preciser la variable de division, sinon il le fait en x
%//et rend une fraction.
%sol:=quo(d,t^2,t);
%//le vecteur QQ doit etre non nul sinon c'est que la courbe est singuliere.
%if egal(QQ,[0,1,0]) then R:=[0,1,0]; else R:=normal(-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:=quo(d,t,t);
%//ce vecteur doit etre non nul.
%R:=expand(-coeff(sol,t,1)*P+coeff(sol,t,0)*Q);
%fi;
%end proc;
%!s!
%!s!<c>
%exemple:
%!s!
%P:=[0,0,1];Q:=[1,1,1];omega:=[0,1,0];
%!s!<c>
%verification egal:
%!s!
% 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);
% pointresiduel(1,-1,0,P,P);pointresiduel(1,-1,0,omega,omega);
%!s!<c>
% addition:
% !s!
%!s!<m>
%plus:=proc(a,b,c,P,Q)
%local R;
%R:=pointresiduel(a,b,c,P,Q);
%R[2]:=-R[2];
%R;
%end proc;
%!s!
%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);
%!s!<c>
%On programme la mult par n en O(log n) additions.
%!s!
%!s!<p>
%nplus:=proc(a,b,c,P,n)
%local Y,m,X;
%Y:=[0,1,0];X:=P;m:=n;
%while m>0 do
% if odd(m) then Y:=plus(a,b,c,X,Y);X:=plus(a,b,c,X,X);m:=(m-1)/2;
%  else X:=plus(a,b,c,X,X);m:=m/2;
%  fi; 
%  end do;
%  Y;
%end proc;
%!s!
%!s!<c>
% Pour verifier que nplus fonctionne, on peut modifier plus pour faire
% l'addition usuelle de 2 vecteurs, de sorte que nplus devra retourner le
% vecteur multiplie par n.
% par exemple:
%plus:=proc(a,b,c,P,Q)
%P+Q;
%end_proc;
%alors nplus(1,2,3,[1,2,5],6) doit donner [6,12,30];
%Autre verification
% Ex: P est d'ordre 2, Q d'ordre 3, P+Q d'ordre 6 
%!s!
% 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);
% pari()
% [x1,x2]:=pari_ellpow([0,1,0,2,-15],[2,1],5);
% [y1,y2,y3]:=nplus(1,2,-15,[2,1,1],5);
% normal([x1,x2]-[y1/y3,y2/y3]);#doit etre nul
% !s!<c> 
%Application \`a la  factorisation.
%!s!
%!s!<p>
%egalomega:=proc(P,N)
% local Q,a,b,c,g;
% 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 g else 1; fi;
%end proc;
%!s!<c>
%factorisation d'un entier via les courbes elliptiques, on cree une fonction
%factell basee sur nplus.
%!s!<p>
%factell:=proc(a,b,c,P,n,N)
%local Y,m,X;
%Y:=[0,1,0];X:=P;m:=n;
%while m>0 and (egalomega(Y,N) == 1 ) do
% if odd(m) then Y:=plus(a,b,c,X,Y);X:=plus(a,b,c,X,X);m:=(m-1)/2;
%  else X:=plus(a,b,c,X,X);m:=m/2;
%  fi;
%  Y:=mods(Y,N); X:=mods(X,N); 
%  end do;
%  egalomega(Y,N);
%end proc;
%!s!
%!s!
%n:=lcm(seq(i,i=1..19));
%!s!<c>
%On cherche c tel que (2,1) soit sur y^2=x^3+bx+c
%!s!
%P:=[2,1,1];N:=nextprime(20000)*nextprime(40000);
%factell(1,2,-15,P,5,N);
%!s!<m>
%for a from 1 to 3 do for b from 1 to 20
%do print(a,b,factell(a,b,P[2]^2-P[1]^3-a*P[1]^2-b*P[1],P,n,N)) od:od:
%!s!
%N:=nextprime(1234567)*nextprime(7654321);n:=lcm(seq(i,i=1..50));
%!s!<m>
%for a from 1 to 3 do for b from 1 to 20
%do print(a,b,factell(a,b,P[2]^2-P[1]^3-a*P[1]^2-b*P[1],P,n,N)) od:od:
%!s!
\newpage
\end{multicols}

\end{document}

