#18589: isogeny efficiency improvement
-------------------------+-------------------------------------------------
Reporter: | Owner:
cremona | Status: needs_review
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:7 jdemeyer]:
> Replying to [comment:5 cremona]:
> > For the rest you need to make a quadratic extension which splits each
into two cubics, and then you have to match the factors.
> I'm wondering if you could use resultants instead...
I thought that we did use resultants... but looking again at Kimi's code,
the relevant function is mult() on line 1960: the effect of this function
is to take the polynomial f and the rational function m, under the
assumption that f is coprime to the denominator of m, and return the poly
whose roots are m(alpha) as alpha runs over the roots of f. If m were a
polynomial that would be res_Y(X-m(Y),f(Y)). I can see now that we could
stil use that formula with m(Y) replaced by the polynomial p(Y) which
satisfies p*d=n (mod f) where m=n/d which would amount to one extended gcd
and one resultant. This may be better than the current code since it does
not use rational functions.
Can we keep this idea for another ticket?
--
Ticket URL: <http://trac.sagemath.org/ticket/18589#comment:9>
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.
