Ways to reduce polynomial modulus irreducible polynomial in F_2

Question

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:

1. How would you solve the second case?
2. Is there a robust method I can follow in solving this kind of reductions besides instincts and trials-and-errors?

Answer 1

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$.

Answer 2

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$.