#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 jdemeyer):
Replying to [comment:9 cremona]:
> 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.
I don't quite get what you're saying here. I think I said "resultants" too
quickly before looking at the actual code.
Mathematically, we need to compute
{{{
gcd( numerator( f(a/b) ), phi)
}}}
where `f`, `a`, `b`, `phi` are univariate polynomials and only `f`
changes. I guess we know that the denominator of `f(a/b)` is `b^d` with
`d` the degree of `f`. So we need
{{{
gcd( b^d f(a/b), phi)
}}}
Now suppose `c` is such that `a/b = c mod phi`, then we really need
{{{
gcd( b^d f(c), phi)
}}}
which equals
{{{
gcd(f(c), phi)
}}}
Now compute this in `R[x]/phi(x)` and this should be the most efficient
way.
(this was written up quickly, I haven't really checked that it's correct)
--
Ticket URL: <http://trac.sagemath.org/ticket/18589#comment:18>
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.
