Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 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 at 4:26

2 Answers 2

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.

share|improve this answer
    
+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 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.