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
    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.