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?


Polynomial long division, and its relative, synthetic division.
For any polynomials $f$ and $g$ (regardless of whether they're irreducible), computing $f$ modulo $g$ is the same as computing the remainder when $f$ is divided by $g$; or to put it another way, it is the same as computing the unique $r$ with $\deg(r)<\deg(g)$ such that $f=qg+r$ for some $q$.
