Powers of polynomials in positive characteristic extremely slow

[Peter Mueller]

In Sage 8.0 I find the following unexpected behavior:

sage: k.<a,b> = GF(2)[]

sage: K.<x> = k[]

sage: f = x^1000 + a*x^500 + b

sage: time f^16

CPU times: user 7.61 s, sys: 8 ms, total: 7.62 s

Wall time: 7.62 s

x^16000 + a^16*x^8000 + b^16

Is it really the case that the exponentiation does not make use of the positive characteristic? Of course I could write a quick function which does what I need in *reasonable* time. But somehow I hope that Sage provides the most basic arithmetic operations, and I simply missed it. What puzzles me even more is this: f^16 takes 7.61 s, but f^1024 takes only 2.04 s. While the latter time is still ridiculous, it seems that for larger exponents some better (yet very poor) algorithm is used.

-- Peter Mueller

[Vincent Delecroix]

Dear Peter,

The power in GF(2)[a,b][x] uses a very generic datastructure and a very
generic power method, see the code at [1]. As you can see, when the
characteristic is > 0 and the power > 20 a special method that explains
the difference seen between f^16 and f^1024.

Did you check how it goes with GF(2)[a,b,x]?

If you have any idea to improve the powering algorithm, Sage is an open
source software that welcomes contribution!

Best
Vincent

[1]
https://github.com/sagemath/sage/blob/master/src/sage/rings/polynomial/polynomial_element.pyx#L2105