Re: miller functions for elliptic curves

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Fri, Feb 04, 2022 at 05:16:52PM +0100, Pierre Charollois wrote:
> I need a function with  divisor m[P] - m[OE], for an elliptic curve over Q,
> and P, Q  arbitrary torsion points.
> I can probably code this naively myself, but maybe there are for instance
> tricks that reduce the number of iterations. (I noticed papers about this).

Most of the papers are for the evaluated version.  For the non-evaluated
version, speed is limited by the size of the output.

You can try the attached script (based on an old script by John Cremona).

E=ellinit("11a1");
P=[5,5]
ellorder(E,P)
f=ellweilpol(E,P,5)

%12 =(150*x^3+(-35*y-2075)*x^2+(-4*y^2+390*y+9400)*x+(y^3+5*y^2-1000*y-14000))/(x^2-32*x+256)

Is it waht you need ?

Cheers,
Bill.

Y;X;
ellequation(e)='Y^2+e.a1*'X*'Y+e.a3*'Y-('X^3+e.a2*'X^2+e.a4*'X+e.a6);

elltang(e,t)=
{
  local(gpt,dyf,dxf,u,v);
  if(t==[0],return(1));
  dyf=2*t[2]+e[1]*t[1]+e[3];
  if(dyf==0,return('x-t[1]));
  dxf=e[1]*t[2]-(3*t[1]^2+2*e[2]*t[1]+e[4]);
  'y-t[2]+(dxf/dyf)*('x-t[1]);
}

ellvert(e,t)=if(t==[0],1,'x-t[1]);

ellchord(e,t,s)=
{
  local(gpt);
  if(s==[0],return(ellvert(e,t)));
  if(t==[0],return(ellvert(e,s)));
  if(s==t,return(elltang(e,t)));
  if(s[1]==t[1],return(ellvert(e,t)));
  'y-t[2]-((t[2]-s[2])/(t[1]-s[1]))*('x-t[1]);
}

ellweilpol(e,t,m)=
{
  local(kt,h);
  if(m==1,return(1));
  if(m==2,return(ellvert(e,t)));
  if(m==3,return(elltang(e,t)));
  kt=elladd(e,t,t);
  h=elltang(e,t);
  for(k=2,m-2,
      h*=ellchord(e,t,kt);
      h/=ellvert(e,kt);
      kt=elladd(e,kt,t)
     );
  h
}