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](http://www.math.clemson.edu/~sgao/papers/GP97a.pdf) 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 \mod 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?



Efficient algorithm for $x^n-x \mod P(x)$ over $GF(2^{12})$
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}$ mod $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}$mod $f$, and you simply subtract $x$ to get the desired $x^{2^n}-x$ mod $f$. You don't even need an extra modulus step, since subtracting $x$ doesn't affect the degree of your result.


