#6008: Improved efficiency of elliptic curve torsion computation
---------------------------+------------------------------------------------
Reporter: cremona | Owner: was
Type: enhancement | Status: new
Priority: minor | Milestone: sage-4.0
Component: number theory | Keywords: elliptic curve torsion
---------------------------+------------------------------------------------
This patch makes an improvement to the efficiency of elliptic curve
torsion subgroup computation (over number fields).
I noticed something in the code I wrote which can be improved. This
is something which was not in Chris Wuthrich's original
implementation, so it is my fault.
Here's what we do: (1) find an upper bound on the torsion order, i.e.
a positive integer N such that the torsion order is certainly a
divisor of N. This uses the function _torsion_bound() in
ell_number_field.py. (2) For each prime dividing N, find a basis
for the p-primary torsion. This is done in
_p_primary_torsion_basis() in ell_generic.py. (3) Put together the
primary parts.
Here's the inefficiency. In step (2) I ignore the bound we have on
the exponent of each prime. This wastes time in computing the
p-primary torsion basis. So I will change the function
_p_primary_torsion_basis() to take an optional parameter which is a
bound on the exponent of the order (not the exponent of the p-primary
subgroup).
e.g. in Jim's example, the bound is 49 and the actual torion is C7xC7. But
when we compute the 7-primary torsion, after finding that the 7-torsion is
complete and of order 49, we do not stop, but test 8 points in the
7-torsion subgroup to see if they can be divided further by 7. that last
part is obiously a waste of time since we have already reached the bound.
Before: Jim's example took 12.64s. After: 9.73s.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/6008>
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
-~----------~----~----~----~------~----~------~--~---
