#4900: [with new patch, needs review] 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 | Resolution:
Keywords: elliptic curves finite fields |
-------------------------------------------+--------------------------------
Changes (by cremona):
* summary: [with patch, not ready for review] New BSGS point counting on
elliptic curves over finite fields => [with new
patch, needs review] New BSGS point counting on
elliptic curves over finite fields
Comment:
The new patch replaces the old. It is based on 3.2.3+#4926 which means
that both the files touched (ell_generic.py and ell_finite_field.py) are
fully sphinxified. It does the following:
1. Implements the new point-counting algorithm much as before.
2. Adds a preliminary computation of l-power torsion for l in [2,3,5]
(depending on the size q of the field) which (when non-trivial) helps the
bsgs routine for finding the order of random points. This part revealed a
bad bug in _p_primary_torsion() which was posted at #4937, but note
that...
3. The bug in #4937 is fixed here.
4. Following malb's comments I have separated out functions
cardinality_sea() and cardinality_pari() to be separate functions, as is
cardinality_bsgs(). None of these caches the result. The main functions
cardinality(), which has the algorithm parameter ('heuristic' by default)
does cache. The 'all' option still does not work as advertised because of
the caching (but then it never did). I think it should be done away with
since testing should be done independently using the cardinality_*()
functions directly. The old cardinality_from_group() function is now
redundant and has been deleted (please don't ask me to deprecate it!)
5. The abelian_group() function is now cleaner and simpler since in all
cases the group order is known at the start.
So I have broken some rules by having this patch deal with #4937 too; by
the time I realised, it was too late to separate the two. As a
consolation I'll add a patch at #4937, based on this one, which adds the
doctest which (as usual) I forgot.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/4900#comment:6>
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
-~----------~----~----~----~------~----~------~--~---
