William Hart on Mon, 26 Feb 2007 15:59:32 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Variable ordering |
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