Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Baby Step Giant Step

  1. Sep 7, 2011 #1
    The baby-step-giant-step method to compute the number [itex]m[/itex] of rational points over an elliptic curve defined over [itex]\mathbb{F}_p[/itex]

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

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

    So [itex]R+iQ[/itex] is always [itex]iQ[/itex], isn't it?
     
    Last edited by a moderator: May 5, 2017
  2. jcsd
  3. Sep 8, 2011 #2
    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 [itex]R+iQ=jP[/itex]. 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]);
    }
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook