Polynomial multiplication modulo polynomial

Question

Suppose we are working on finite field $F_{16}$ and have pritimive polynomial $z^4+z+1$. I stuck at how to compute polynomial modulo. For example, we have $z^5+z+1$ mod $z^4+z+1$. I use the usual division, I obtain the remainder is $-z^2+1=z^2+1$ because each coefficient is over $F_2$. But I don't know whether this is the correct way to compute remainder. Can anyone help me?

Answer 1

I am assuming that $z^4+z+1$ is the irreducible polynomial used to construct the field $\mathbb{F}_{16}$ (this is different from the concept of primitive element). In that case $z^4+z+1 \equiv 0$.

\begin{align*} z^4+z+1 & \equiv 0 \pmod{z^4+z+1}\\ z^4 & \equiv z+1 \pmod{z^4+z+1}\\ z^5 & \equiv z^2+z \pmod{z^4+z+1}\\ z^5+z+1 & \equiv z^2+1 \pmod{z^4+z+1} \end{align*} So you have the right answer but using the above congruences can help you reduce your work.

Answer 2

In general, long division will always give you the right answer, but is often tedious. An approach like in Anurag A's answer will often make that calculation easier, but sometimes requires a bit of cleverness.

As for the example in your comment, a similar idea works. If you're computing modulo $x^{2}-1$, you're saying that $x^{2} -1 \equiv 0$, or $x^{2} \equiv 1$. So, we get:

$$ x^{3} + 2x^{2} = x \cdot x^{2} + 2 \cdot x^{2} \equiv x \cdot 1 + 2 \cdot 1 = x+2 . $$

I'm thinking you should double check your long division on that one.