#4900: New BSGS point counting on elliptic curves over finite fields
---------------------------+------------------------------------------------
Reporter: cremona | Owner: was
Type: enhancement | Status: new
Priority: minor | Milestone: sage-3.4
Component: number theory | Keywords: elliptic curves finite fields
---------------------------+------------------------------------------------
Point counting on elliptic curves where the j-invariant is not in the
prime field has been implemented up to now via the same function that
determines the group structure. The reason was that "Mestre's trick" does
not always work over non-prime fields (specifically, over F_q where q is
square there are always counterexamples). I worked out how to extend
Mestre to the general case about 9 months ago but did not want to
contribute the resulting code until it was written up. That has now been
done, in a 4-page note joint with Drew Sutherland. (See
http://www.warwick.ac.uk/staff/J.E.Cremona/papers/MestreNote.pdf; it
should be on ArXiV early January 2009).
The current patch implements this in a new function cardinality_bsgs().
This will always be used in computing the cardinality of curves whose
j-invariant is not in the prime field. Over prime fields it can be used
by giving algorithm='bsgs' to the cardinality() function. [The old use of
algorithm='bsgs' is renamed algorithm='pari' since that's the option to
call pari, which is only over prime fields.]
This also means that the abelian_group() function is simpler since it
always computes the cardinality first, which simplifies that code.
Lastly, the new code uses quadratic twists, and the quadratic_twist()
funtion in ell_generic.py can now be called with no twisting parameter for
curves over finite fields, with the single exception of characteristic 2
and j=0.
The patch applies to 3.2.2 and has been tested on lots of curves
(including all the -long tests in sage/schemes/elliptic_curves).
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4900>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
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-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
