John, Thanks. No, actually the curves are supersingular over GF(p^2) so the group is always the product of two cyclic groups of the same order (as far from cyclic as you can be). I guessed that once I calculated the group order, it was cached, and then it was attempted to be factored (which, in this case was easy), and then you're home free.
Victor On Thursday, August 15, 2013 10:20:49 AM UTC-7, John Cremona wrote: > > I should be able to answer this having written the underlying code (a few > years ago though). > Finding the group order will involve finding orders of random points. If > the group is cyclic (I did not check) then it will quickly obtain that > information and then finding the orders of any other points will be easy. > In that case it is quite possible that when you find the order of a random > point you will find that it lies in the Hasse interval and hence the group > is cyclic, in which case the group order is cached even though it was not > asked for, to speed up finding the order of subsequent points. > > If not cyclic, then no random point will be a generator so finding the > order of one point will not cause any info to be cached to help finding the > orders of more points, while if you actually ask for the group order -- > which will in this case be harder and involve some Weil pairings, etc -- > then finding point orders after that will be faster. > > I think what this means is that as soon as you find the order of a point > on a curve whose group order has not yet been computed and cached, that > information should be cached. > > I hope this makes some sense! > > 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.
