Baby Step Giant Step: Computing m of Rational Points on Elliptic Curve

[yavanna]

The baby-step-giant-step method to compute the number m of rational points over an elliptic curve defined over \mathbb{F}_p

http://img560.imageshack.us/img560/3852/babym.jpg
Uploaded with ImageShack.us

In the second part R=(p+1)P, but for every point on the curve (p+1)P is the identity element of the group: P_{\infty}.

So R+iQ is always iQ, isn't it?

 

[yavanna]

I've tried to use this algorithm in PARI/GP with the following code, just to check if it works, it doesn't output m but the indexes [i,j] of R+iQ=jP. Ellpoint finds a random point on the curve, ellsum makes the sum between two points, ellpow(E,P,n) compute the scalar multiplication nP. But it doesn't work

{\\Baby-Step-Giant-Step E(F_p)
BSGS(e,char)=local(s,i,v,P,Match,j,Q,R,S,k);
s=ceil(char^(1/4));
P=ellpoint(e,char);
v=vector(s);
v[1]=P;
for(i=2,s,v=ellsum(e,v[i-1],P,char));
for(i=1,s,v=concat(v,[[v[1],-v[2]]]));
print(v);
Match=0;
Q=ellpow(e,P,2*s+1);
R=ellpow(e,P,char+1); j=0;
while(Match==0,j=j+1;S=ellpow(e,Q,j);print(S);for(i=1,s,if(S==v,Match=1;k=i,) )\\end for
);\\end while
return([k,j]);
}