On Sunday 18 November 2007, David Harvey wrote: > 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?
Hi David, I cannot see any restriction placed on the curves or the fields used. Justin pointed me to the errate for Washington's book but it only contains the remark, that the greatest common multiple is indeed the least common multiple. Revisiting the group structure of elliptic curves I now also cannot see why this algorithm would work: the group of points of an elliptic curve over a finite field is either isomorphic to Z_n or Z_n1 + Z_n2 where n1 | n2 (also from Washington's book). In the later case we'll have points of orders n1 and n2 and their LCM will be n2. So the trac ticket should be invalidated. Does this sound about right? Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _www: http://www.informatik.uni-bremen.de/~malb _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to [email protected] 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/ -~----------~----~----~----~------~----~------~--~---
