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. 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 sage-support...@**googlegroups.com. >>> To post to this group, send email to [email protected]. >>> >>> Visit this group at >>> http://groups.google.com/**group/sage-support<http://groups.google.com/group/sage-support> >>> . >>> For more options, visit >>> https://groups.google.com/**groups/opt_out<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.
