inefficient polynomial powering for positive characteristic

[robertwb]

One can take advantage of the fact that (a+b)^p = a^p + b^p to quickly expand fⁿ = f^qp * f^r (as r<p, and f^p is sparse, the resulting product is easy to compute).

See http://groups.google.com/group/sage-support/browse_thread/thread/38c3d619a7684a90

Upstream: Fixed upstream, in a later stable release.

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/7253

[robertwb]

Description changed:

--- 
+++ 
@@ -1,3 +1,3 @@
-One can take advantage of the fact that (a+b)<sup>p</sup> = a<sup>p</sup> + b<sup>p</sup> to quickly expand f<sup>n</sup> = f<sup>qp</sup> * f<sup>r</sup> (where r<p, so one can literally write out the resulting monomials). 
+One can take advantage of the fact that (a+b)<sup>p</sup> = a<sup>p</sup> + b<sup>p</sup> to quickly expand f<sup>n</sup> = f<sup>qp</sup> * f<sup>r</sup> (as r<p, and f^p is sparse, the resulting product is easy to compute). 
 
 See http://groups.google.com/group/sage-support/browse_thread/thread/38c3d619a7684a90

[kedlaya]

Upstream: Reported upstream. No feedback yet.

[kedlaya]

comment:2

This behavior still appears to be present in 2016. Since the underlying representation of multivariate polynomials over a finite field appears to be in Singular, I've raised the issue upstream:

http://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=2523

For univariate polynomials over a finite field, the underlying representation is in FLINT, and there this seems to be handled correctly (although I haven't looked at the source or asked a developer to confirm):

sage: F = GF(7)
sage: P.<x> = PolynomialRing(F)
sage: u = (x^3 + 1)^3
sage: time v = u^(7^7); # a large power!
CPU times: user 1.17 s, sys: 44 ms, total: 1.21 s
Wall time: 1.21 s
sage: time v = u^1000000; # even larger! 
CPU times: user 1.58 s, sys: 36 ms, total: 1.62 s
Wall time: 1.62 s

[kedlaya]

Changed upstream from Reported upstream. No feedback yet. to Fixed upstream, in a later stable release.

[kedlaya]

comment:3

This has been resolved upstream (see previous Singular link), so I propose to close this ticket.