That is about right. Also n_2 divides q-1 where q is the field order, which is also useful for cutting down the possibilities.
However you cannot compute the group order _just_ by computing the orders of random elements. For example, structures 2*8 and 16 would not be distinguished unless you happened to pick a point of order 16. John On 19/11/2007, Martin Albrecht <[EMAIL PROTECTED]> wrote: > > 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] > > > > > -- John Cremona --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
