#18547: Improve polynomial powering in positive characteristic
-------------------------------------+-------------------------------------
Reporter: bruno | Owner:
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.8
Component: commutative | Resolution:
algebra | Merged in:
Keywords: polynomial, | Reviewers:
powering | Work issues:
Authors: Bruno Grenet | Commit:
Report Upstream: N/A | 7760a4306328684b58752e095b84991c66a3996c
Branch: | Stopgaps:
u/bruno/polynomial_powering_positive_characteristic|
Dependencies: |
-------------------------------------+-------------------------------------
Changes (by bruno):
* status: needs_work => needs_review
Comment:
The algorithm I proposed was completely wrong: If `p` is the
characteristic and `n=p * q + r`, I used the **wrong** identity `f(x)^n =
f(x^{p*q}) * f(x)^r` instead of the correct `f(x)^n = f(x^p)^q * f(x)^r`.
In the commit, I correct this mistake, and in the same time I take
[comment:10 jdemeyer]'s comments into account:
- I add doctests for the different possibilities. (Note that I wrote code
for the case where the base ring is a finite field and the polynomials are
in dense representation, though as I wrote [comment:9 above] this code is
not used since there is specific code in `polynomial_template.pxi`. Thus
there is no doctest for this case.)
- "Of course", it is not "of course mandatory" for the base ring to be a
finite field...
--
Ticket URL: <http://trac.sagemath.org/ticket/18547#comment:13>
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.
