# Polynomial multiplication modulo polynomial

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?

-
is the polynomial $x^4+x+1$ used to construct the field as in $\mathbb{Z}_2[x]/\langle x^4+x+1\rangle$? – Anurag A Jun 23 '14 at 4:21
doc.ic.ac.uk/~mrh/330tutor/ch04s02.html i refer to this website. For $x^3+2x^2$ mod $x^2-1$, I don't understand how the author obtains $x+2$. I use normal long division to solve, I obtain the remainder is $x-1$ – Idonknow Jun 23 '14 at 4:26

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.

-
+1 But $z^4+z+1$ is a primitive polynomial. It is the most popular choice for a primitive quartic over $\Bbb{F}_2$. Mind you, there isn't much competition as the reciprocal $z^4+z^3+1$ is the only other quartic primitive polynomial. Consequently any zero of $z^4+z+1$ in this field is a primitive element. – Jyrki Lahtonen Jun 23 '14 at 5:24

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.

-