On Nov 19, 2007 6:33 AM, David Harvey <[EMAIL PROTECTED]> wrote: > > > > On Nov 19, 2007, at 4:55 AM, Martin Albrecht wrote: > > >> 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? > > Yeah. > > So I guess either you have to look at John Cremona's code, figure out > how difficult it would be to wrap, or look up another algorithm and > implement that instead. > > Further down the road, Drew Sutherland is thinking about writing a C+ > + library for computing things like orders, exponents, structures of > generic abelian groups. Basically you give it a "black box" that > knows how to add group elements, invert group elements, produce the > identity, and produce random elements, and it efficiently works out > the structure of the group, etc. No firm plans yet though.... I'm
How do you produce a random element without knowing the generators of the group? And, for an abelian group, the generators give you the "invariants" quickly don't they? > meeting up with him next week to discuss this. It will be some time > before it's written and wrapped in sage. > > 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/ -~----------~----~----~----~------~----~------~--~---
