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

share|improve this question
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? –  Isomorphism Dec 14 '12 at 5:18
    
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. –  anon Dec 14 '12 at 5:19
    
@Isomorphism I think your answer makes the most sense, and I updated my question if you could take a look. –  Not a NaN notha Dec 14 '12 at 8:12
1  
Yes. The reasoning in your edit is correct :) –  Isomorphism Dec 14 '12 at 8:19
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. –  Jyrki Lahtonen Dec 14 '12 at 8:19
add comment

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
add comment

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.