<s>[INST] 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?
 [/INST] 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.
</s>