Ways to reduce polynomial modulus irreducible polynomial in F_2 Thank you all in advance for the help. I really appreciate your time in answering this question.

I am trying to find a good summary of ways to reduce polynomial modules irreducible polynomial in $F_2$. Examples of exercise I have run through are:


$x^{21}$ mod $x^5+x+1$

can be solved by fast exponentiation as follow

$x^{21}=((x^5)^2)^2 x=((x+1)^2)^2x=(x^4+1)x=x^5+x=1$ mod $x^5+x+1$


However, when I try to solve

$x^{31}$ mod $x^5+x^2+1$

the same method doesn't work.
I do notice that it may be easier to solve instead

$x^{32}$ mod $x^5+x^2+1$

then multiply by multiplicative inverse of x found by Euclidean algorithm. But even this I failed to solve.

My questions are:


*

*How would you solve the second case? 

*Is there a robust method I can follow in solving this kind of reductions besides instincts and trials-and-errors?


Fermat's Little Theorem applies to finite fields: If $K$ is a field with $q$ elements, then $a^q = a$ for all $a\in K$.
Since $\mathbb{F}_p [X] / f(x)$ is a field of $p^{\deg f}$ elements when $f$ is irreducible, we can apply this to your example.
In particular, we have $x^{32} = x^{2^5} \equiv x \pmod{x^5+x+1}$.  Dividing, we have $x^{31} = x^{-1} x^{32} \equiv x^{-1} x \equiv 1$.
