John, Now I understand. I will open a ticket. I'd suggest that we add a new private method which will look at the curve and return True if it's one that has a fast method for computing the order. I haven't looked, but is there sage code to compute Hecke characters, which is what's necessary to deal with curves with CM with small discriminants?
Victor On Saturday, August 17, 2013 9:44:49 AM UTC-7, John Cremona wrote: > > 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] > <javascript:>>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] <javascript:>. >> To post to this group, send email to [email protected]<javascript:> >> . >> 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.
