Michael Stoll said at SD6 that he had written such a generic program in Magma. You could ask him to dig it out and pass it on.
For the specific elliptic curve case I'm sure that using a custom program will be better in many respects, since you know so much more about the group structure's possibilities, and also have tools such as the Weil pairing available (if implemented!) which gives the thing more structure than just an abelian group with at most two cyclic components. I have half-written notes on how I implemented this -- which I though worth doing as I was making it quite a bit more efficient than the LiDIA code I started from -- which I can pass on to anyone ineterested (I already sent them to malb) but of course it would be better to finish writing them first... John On 19/11/2007, 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 > meeting up with him next week to discuss this. It will be some time > before it's written and wrapped in sage. > > david > > > > > -- 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/ -~----------~----~----~----~------~----~------~--~---
