I* haven't looked at the code, but does "finding the order of random points" use baby step giant step, or some sort of version of Pollard rho or lambda?
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.
