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 --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
