On 19 August 2013 08:59, John Cremona <[email protected]> wrote:
> On 19 August 2013 01:29, Victor Miller <[email protected]> wrote: > >> 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? >> >> > I think not. Let's keep the first ticket limited to the cases j=0, 1728 > which will be very easy, and have a second ticket for the larger task of > dealing with other small discriminants. > > Victor, did you make a ticket? I could not find it. John John > > >> 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]> 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. >> > > -- 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.
