I know what it is -- I had not looked at the specific curve when I first answered. Your curve has j-invariant 0, and when j=0 or 1728 the cardinality of the group is computed using the formula (taking into account twists of course) so is instantaneous. But the finding of orders of points will use BSGS (there is a Pollard rho method too, implemented by someone else).
So this is wirth at least one patch: when computing the order of a point it does check to see if the group order is already known, and makes use of that if it is, otherwise uses BSGS taking into account the Hasse interval to find a multiple of the point order which lies in that interval, which it then factors. (You can fill in further details for yourself, or look at the source code). The easy patch would be that if the group order is not known yet but j=0 or 1728 then the group order should be computed right then, since it is easy. A more general improvement would be to enlarge the set of j-invariants for which the group order was computed by formula, say to include the other class number 1 j-invariants. A project for someone! Victor, feel free to open a ticket with my first suggestion, which would be very easy to implement. John On 15 August 2013 02:24, Victor Miller <[email protected]> wrote: > Consider the following: > def NextProgression(n,a,q): > p = next_prime(n) > while (p%q) != a: > p = next_prime(p+1) > return p > def Test(n,compute=False): > p = NextProgression(n,2,3) > print "found prime=",p > F.<u> = GF(p^2) > print "Found field" > E = EllipticCurve(F,[0,1]) > if compute: > NN = E.order() > print "Found Elliptic Curve of order ",NN > P = E.random_point() > Q = E.random_point() > print "Found points" > nP = P.order() > print "Found order of P" > nQ = Q.order() > print "Found order of Q" > N = lcm(nP,nQ) > return E,P,Q,N > > time E,P,Q,n = Test(2^25) > > > found prime= 33554501 > Found field > Found points > Found order of P > Found order of Q > Time: CPU 10.52 s, Wall: 10.77 s > > > > time E,P,Q,n = Test(2^25,compute=True) > > > found prime= 33554501 > Found field > Found Elliptic Curve of order 1125904604468004 > Found points > Found order of P > Found order of Q > Time: CPU 0.17 s, Wall: 0.18 s > > > > I understand that knowing the order of E is necessary to find the order of > points, but why should forcing the order of E to be computed first make it > almost 60 times faster? > > Victor > > This was on sage 5.11 on my macbook > > > > > -- > You received this message because you are subscribed to the Google Groups > "sage-support" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > Visit this group at http://groups.google.com/group/sage-support. > For more options, visit https://groups.google.com/groups/opt_out. > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
