On Nov 18, 2007, at 8:49 AM, Martin Albrecht wrote:
> > On Sunday 18 November 2007, David Harvey wrote: >> On Nov 18, 2007, at 4:16 AM, Robert Bradshaw wrote: >>>> #1130 >>> >>> This seems to rely on an earlier patch. (#1120?) See comments on >>> trac. >> >> I'm very concerned about this patch. It is not the case that the LCM >> of the orders of all elements of E(GF(q)) will equal the order of E >> (GF >> (q)). I haven't tried the code, but if I understand the code >> correctly, it will go into an infinite loop on such cases, and it may >> well give incorrect results in other cases. > > Yes, it should not go in, my bad, sorry. I quickly hacked to > together the > algorithm in "Elliptic Curves" by Lawrence Washington and > apparently screwed > up badly on the way. He writes: > > 7. If we are looking for the #E(F_q), then repeat steps (1)-(6) > [finding the > order of a point, malb] with randomly chosen points in E(F_q) until > the > greatest common multiple of the orders divides only one integer N > with q + > 1 -2*sqrt(q) <= N <= q + 1 + 2*sqrt(q). Then N = #E(F_q). > > Apparently I overread the 'divides' part. Also, what is a > 'greatest common > divisor'? I still don't believe this algorithm. Look at this example: sage: K.<a> = GF(3^4) sage: K.polynomial() a^4 + 2*a^3 + 2 sage: E = EllipticCurve(K, [2*a^2 + 2*a + 2, 2*a^3 + 2*a + 1]) sage: points = E.points() sage: len(points) 100 sage: LCM([P.order() for P in points]) 10 The hasse bound says the the number of points must be in [64, 100]. But if the best we can do is show divisibility by 10, that's not enough information: it could be 70, 80, 90, or 100. Does Washington place any other restrictions on the finite field or on the curve? david --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
