1
$\begingroup$

Suppose we have polynomials over $GF (2^8)$.

$a(x) = x^8$.

$m(x) =x^8+x^4+x^3+x+1$

A textbook says that.

$x^8 \bmod m(x) = [m(x) - x^8]=(x^4+x^3+x+1)$

So I would like to understand, how do we reach this answer?

It's unclear to me how we perform division here when $m(x) > a(x)$. All the examples in the book show division or finding $a(x) \bmod m(x)$ when $m(x) < a(x)$.

EDIT

If I understand the comments correctly, $x^8+x^8 = x^8-x^8=0 $ since this is GF$(2)$. So then $ -x^8 + -(x^4+x^3+x^1+1) = -m(x) $, so if $r(x) =(x^4+x^3+x^1+1)$, then $a(x)-r(x) \equiv 0 \bmod m(x)$. Do I have this correct?

  • 1
    In your case, the field has characteristic $2$, so $- x^8 = x^8$. By definition, $a(x) = b(x) \text{ mod } m(x)$ iff $m(x)$ divides $a(x) - b(x)$. Do you see it now?2012-12-14
  • 0
    You reach that answer with $x^8=-x^8$ and $p(x)=p(x)\pm m(x)$ for all polynomials $p$. When $m>a$, there is nothing to do, just as if you were dividing with integers.2012-12-14
  • 0
    @Isomorphism I think your answer makes the most sense, and I updated my question if you could take a look.2012-12-14
  • 1
    Yes. The reasoning in your edit is correct :)2012-12-14
  • 1
    The problem is perhaps with your interpretation of $>$. With polynomials you should think of the degree of a polynomial as a measure of its "size". So you look for a remainder of as small a degree as possible. It is always possible to find a (unique) remainder that has lower degree than the divisor. Here the divisor has degree 8, so a degree 8 remainder will not do. You have to get rid of the degree eight term. IOW two polynomials of degree 8 are not comparable in the sense that you could declare one being "larger" than the other.2012-12-14

1 Answers 1

3

Another way to think of it is that you're trying to figure out what happens to $a(x)$ inside $k[x]/\langle m(x) \rangle$, where $k=GF(2^8)$. In other words, when you take your polynomial $a(x)\in k[x]$ and send it over to the quotient $k[x]/\langle m(x) \rangle$, you're living in a word where $$x^8+x^4+x^3+x+1=0,$$ so if that $a(x)$ happens to be $x^8$, figuring out the image is easy: $$x^8=-\left(x^4+x^3+x+1\right),$$ which in this case is equivalent to $$x^8=x^4+x^3+x+1$$ since we're in a binary field.