inefficient polynomial powering for positive characteristic

[Robert Bradshaw]

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

[Kiran Kedlaya]

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

[Kiran Kedlaya]

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