Variable ordering

[William Hart <hart_wb@yahoo.com>]

Hi all,

I can't seem to find a solution to the following
problem. It's a long post, but the problem is quite
simple, I've just taken some time to characterise it
as well as possible.

I'm implementing an algorithm for converting from one
kind of curve to another. Along the way I have to do
lots of plugging values and polynomials into other
polynomials and functions.

Here is roughly the code I'm using (I've simplified it
so you don't have to read as much unrelated nonsense).
You can pretty much ignore the function QpPoint. It
works fine, but I've just included it for
completeness. The problems occur in the function
toEllipticCurve, as discussed below the program trace:

======================================================
/* Pari program */

/* A list of coefficients for cubic curves */
sha3=[[1,2,91,0,0,0,0,0,0,-17],[2,7,13,0,0,0,0,0,0,-17],[1,7,26,0,0,0,0,0,0,-17],[1,13,14,0,0,0,0,0,0,-17]];

p = 3;
n = 5;
prec = 30;

/* A function to find a p-adic point on my curve C */

QpPoint(C,p) = 
{
  
curve=C[1]*u^3+C[2]*v^3+C[3]+C[4]*u^2*v+C[5]*u^2+C[6]*u*v^2+C[7]*v^2+C[8]*u+C[9]*v+C[10]*u*v;
   print(curve);print("");
   i=1;
   fi = subst(curve,u,i);
   roots =
polrootspadic(fi,3,max(30,valuation(poldisc(fi),p)));
   while(length(roots) == 0,
      i=i+1;
      fi = subst(curve,u,i);
      roots =
polrootspadic(fi,3,max(prec,valuation(poldisc(fi),p)));
   );
   print("Curve has rational point
[",i,",",roots[1],"]");print("");
   return([i,roots[1]]);
}

/* The function which I am having a problem with
(somewhat simplified)*/

toEllipticCurve(C,P) =
{  
f(u,v)=C[1]*u^3+C[2]*v^3+C[3]+C[4]*u^2*v+C[5]*u^2+C[6]*u*v^2+C[7]*v^2+C[8]*u+C[9]*v+C[10]*u*v;
   P[2]=Mod(w,f(P[1],w));
   f0(u,v)=f(u+P[1],v+P[2]);
   print(f0(u,v));
/* Here's where the first problem occurs, see below */
   f1(U,V,W)=(W^3)*f0(U/W,V/W);
   print(f1(U,V,W));

   s8=polcoeff(polcoeff(f1(U,V,W),2,W),1,U);
  
s9=polcoeff(polcoeff(polcoeff(f1(U,V,W),2,W),0,U),1,V);
  
e2=subst(subst(polcoeff(f1(U,V,W),1,W),U,s9),V,-s8);
  
e3=subst(subst(polcoeff(f1(U,V,W),0,W),U,s9),V,-s8);
   /* Things have already 
gone completely wrong.... see below */
  
f2=subst(subst(subst(f1(U,V,W),U,Ud-(s9*e2/e3)*Wd),V,Vd+(s8*e2/e3)*Wd),W,Wd);
   print(f2);
   f2=subst(subst(subst(f2,Wd,1),Ud,ud),Vd,vd);
   print(f2);
}

/* The main program, which just calls the above
functions*/

main() = 
{
   C=sha3[1]; /* Let C be one of the curves */
   P = QpPoint(C,p); /* Find a point on that curve*/
   E=toEllipticCurve(C,P); /* Convert the curve */
}

main();    

======================================================


So here's the problem. In the function
toEllipticCurve, the first print statement prints
something like the following:

u^3 + 6*u^2 + (-17*v + Mod(-17*w + 12, 2*w^3 - 34*w +
99))*u + (2*v^3 + Mod(6*w, 2*w^3 - 34*w + 99)*v^2 +
Mod(6*w^2 - 34, 2*w^3 - 34*w + 99)*v)

As you can see, it is a polynomial in u and v with
coefficients in Z[w]/(3*w^3+2*w^2+w-1).

Now all I want to do is replace u with U/W and v with
V/W in this polynomial. I've tried using the Pari
subst function (with appropriate modifications to the
code). And I've tried exactly what I've written in the
program  trace above. But it doesn't work. Here is the
result:

Mod(6*W^2*V*w^2 + (-17*W^2*U + 6*W*V^2)*w + (U^3 +
6*W*U^2 + (-17*W*V + 12*W^2)*U + (2*V^3 - 34*W^2*V)),
2*w^3 - 34*w + 99)

Now I realise this is a Pari variable order issue, and
indeed, if I change the order of the Pari variables
using the reorder command, it works just fine. If I
don't, all of e2, e3, s8 and s9 end up being 0, which
of course causes a divide by zero error on the next
few lines. But having gotten this bit to work (see
below for a modified function which works at least
this far), we can keep moving.

But then we come to the next bit. No amount of
variable reordering makes this work how one imagines
it should. I appear to be completely unable to get the
particular substitutions there to work.

Does someone know how to do these kinds of
substitutions without having to use the Pari reorder
command, or how to use the reorder command in this
instance to make it return a correct answer?

For those who want to play with this further, below is
a version of this same problematic function, but which
returns the correct result up to and including (up to
for French readers) the computation of s8,s9,e2 and
e3. After that, I cannot get it to work. I've tried
the reorder command and changing everything over to
polynomial substitutions as in the above version of
the function. 

I've tried using local variables, but this doesn't
work, as they all appear to be set to 0, which isn't
what you want for a variable that you want to use in a
rational function.

=====================================================

toEllipticCurve(C,P) =
{
   reorder([U,V,W,u,v,w]);
  
f=C[1]*u^3+C[2]*v^3+C[3]+C[4]*u^2*v+C[5]*u^2+C[6]*u*v^2+C[7]*v^2+C[8]*u+C[9]*v+C[10]*u*v;
   P[2]=Mod(w,subst(subst(f,u,P[1]),v,w));
   f0 = subst(subst(f,u,u+P[1]),v,v+P[2]);
   f1=(W^3)*subst(subst(f0,u,U/W),v,V/W);
   print(f1);
   s8=polcoeff(polcoeff(f1,2,W),1,U);
   s9=polcoeff(polcoeff(polcoeff(f1,2,W),0,U),1,V);
   e2=subst(subst(polcoeff(f1,1,W),U,s9),V,-s8);
   e3=subst(subst(polcoeff(f1,0,W),U,s9),V,-s8);
/*everything is fine until here. In particular
s8,s9,e2 and e3 are what you expect them to be, and
not zero*/
     
f2=subst(subst(subst(f1,U,Ud-(s9*e2/e3)*Wd),V,Vd+(s8*e2/e3)*Wd),W,Wd);
   print(f2);
   f2=subst(subst(subst(f2,Wd,1),Ud,ud),Vd,vd);
   print(f2);
/*but by now, any attempt to do anything with f2 will
return incorrect answers, usually 0. This is
especially the case if I try to do any variable
reordering.*/
   /*.....*/
}

=====================================================

I'd appreciate any help anyone can give me, as it is
driving me insane. Pari ought to be able to do simple
substitutions like this!

Regards,

Bill Hart
Warwick Uni.


 
____________________________________________________________________________________
Do you Yahoo!?
Everyone is raving about the all-new Yahoo! Mail beta.
http://new.mail.yahoo.com