#11095: Add BMSS algorithm for isogenies of elliptic curves
-------------------------------+--------------------------------------------
Reporter: defeo | Owner: cremona
Type: enhancement | Status: needs_review
Priority: minor | Milestone: sage-4.7
Component: elliptic curves | Keywords: isogenies
Work_issues: | Upstream: N/A
Reviewer: | Author: Luca De Feo
Merged: | Dependencies:
-------------------------------+--------------------------------------------
Changes (by defeo):
* status: new => needs_review
Old description:
> Add the algorithm by Bostain, Morain, Salvy and Schost for normalized
> cyclic isogenies in characteristic 0 or large enough.
>
> References:
>
> [BMSS08] Alin Bostan, François Morain, Bruno Salvy, and Éric Schost, Fast
> algorithms for computing isogenies between elliptic curves, Mathematics
> of Computation 77 (2008), 1755–1778.
New description:
Add the algorithm by Bostain, Morain, Salvy and Schost for normalized
isogenies in characteristic 0 or large enough.
References:
[BMSS08] Alin Bostan, François Morain, Bruno Salvy, and Éric Schost, Fast
algorithms for computing isogenies between elliptic curves, Mathematics of
Computation 77 (2008), 1755–1778.
--
Comment:
Besides implementing BMSS, I cleaned a bit `ell_curve_isogeny`, moving the
algorithms that do not work in any characteristic to a new module
`ell_isogeny_char_zero`. In my view, only the `EllipticCurveIsogeny` class
and Vélu/Kohel formulae should remain in ell_curve_isogeny` in the end.
BMSS runs significantly faster than Stark's, and works for slightly larger
characteristics, I thus set it as the default choice. I haven't produced
any serious benchmarks, but I will if the reviewers ask me to.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/11095#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
