Efficient algorithm for $x^n-x \bmod P(x)$ over $GF(2^{12})$

Question

My goal is to generate an irreducible polynomial over $GF(2^{12})$ with degree $t$, which can get fairly big, let's say up to $t=200$ or so. I've found this very helpful paper that walks me through the Ben-Or irreducibility test. I've implemented it, and it works perfectly for, um, $t\le5$.

Part of the algorithm requires computing $x^{q^i}-x \bmod f$, where $f$ is a randomly-generated degree $t$ polynomial, the order $q=2^{12}$, and $i$ gets as high as $\frac{t}{2}$. I have a decently efficient adaptation of long division to compute the modulus. Unfortunately I'm using a polynomial library (JLinAlg, for Java) where the degree is represented as a 32-bit signed integer: $2^{q^i}$ is too large for $i>2$.

One option, of course, would be to re-implement polynomials to represent the degree with an arbitrarily large number. But I wonder, since I'm working in a field with characteristic $p=2$ and my dividend is so specific, if there's a better solution that doesn't require the big numbers at all?

Answer 1

OP here. Achim Krause gave the answer in his comment on my question; I'm putting it here to show the question is resolved.

You can compute $x^{2^n} \bmod f$ by starting with $x$, and then repeatedly squaring and reducing modulo $f$ in each step. Takes you $n$ steps, and the degree of none of the intermediate values gets larger than twice the degree of $f$.

Now you have $x^{2^n} \bmod f$, and you simply subtract $x$ to get the desired $x^{2^n}-x \bmod f$. You don't even need an extra modulus step, since subtracting $x$ doesn't affect the degree of your result.