#18589: isogeny efficiency improvement
-------------------------+-------------------------------------------------
Reporter: | Owner:
cremona | Status: needs_work
Type: | Milestone: sage-6.8
enhancement | Resolution:
Priority: major | Merged in:
Component: | Reviewers:
elliptic curves | Work issues:
Keywords: | Commit:
isogeny | 47ccfd587402b953c612fcd3cddaa541a6847bd3
Authors: John | Stopgaps:
Cremona |
Report Upstream: N/A |
Branch: |
u/cremona/18589 |
Dependencies: |
-------------------------+-------------------------------------------------
Comment (by cremona):
Replying to [comment:33 jdemeyer]:
> Replying to [comment:14 cremona]:
> > Without the patch though I would not have been able to compute this:
http://beta.lmfdb.org/EllipticCurve/2.2.89.1/81.1/a/ !!
>
> I'm actually curious why you get a huge speed-up here. I can see that
the patch here improves things, but to go from "not being able to compute"
to "being able to compute" surprises me. Doesn't the computation and
factoring of the division polynomial dominate the whole computation
anyway?
Its computation is short, and its factoring takes < 1 hour. In the code I
had, computing the complete isogeny class of 4 curves, I had to do that 4
times. (I am working on not having to recompute the kernel polys for
other curves in the isogeny class, but that will definitely be another
ticket). I also had some lines like E1.is_isogenous(E2,proof=True) which
triggered computation of the whole isogeny class of E1. (With proof=False
it just checks traces of Frobenius but I also had curves which were not
isogenous but whose traces agreed at a lot of primes, so was playing
safe).
--
Ticket URL: <http://trac.sagemath.org/ticket/18589#comment:34>
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
