Re: halving points on elliptic curve

[Karim Belabas <Karim.Belabas@math.u-bordeaux1.fr>]

* somayeh didari [2013-09-25 10:06]:
> thanks for your help, I wrote this program, which take elliptic curve e over the rational points and a point Q in e and returns (1/2)Q:
> halve(e,Q)={
> x_0=Q[1];
> Half=[];
> f=x^4-e.b4*x^2-2*e.b6*x-e.b8-x_0*(4*x^3+e.b2*x^2+2*e.b4*x+e.b6);
> g=factor(f);
> v=[];
>  for(i=1,#g~,
> if(poldegree(g[i,1])==1,
> v=concat(v,-polcoeff(g[i,1],0)/polcoeff(g[i,1],1));
>    );
> );
> for(i=1,#v~,
> x=v[i];
> y=ellordinate(e,x)[1];
> if(ellpow(e,[x,y],2)==Q,
> Half=concat(Half,[[x,y]]);
> );
> if(ellpow(e,[x,-1*y],2)==Q,
> Half=concat(Half,[[x,-1*y]]);
> );
> );
> }
> It works!

No, it doesn't.

Your initial "f" uses the *value* of the GP variable "x", where you
intended to use a formal polynomial variable. Since your code later sets
x = v[i], we in fact know for sure that the second time this is called,
f will not be a polynomial, but a numeric (rational) value.

A few pointers:

1) indent your code, the above is painful to read

2) declare all your local variables with my(), you will avoid the above
problems. Don't use global variables, replace by return(Half);

3) use Pol([1,2,3], 'x)  instead of x^2 + 2*x + 3  (note the 'x, this
means "the formal variable x, not the value of the GP variable x")

4) as already suggested, use nfroots(,f), instead of factor() + hunting
for linear factors

There quite a few more possibilities for improvements, but let's start
with the above.

Cheers,

    K.B.
--
Karim Belabas, IMB (UMR 5251)  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux1.fr/~kbelabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux1.fr/  [PARI/GP]
`