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.

I am currently studying for an exam and trying to check a message (binary) for errors using a polynomial, I would like if somebody could verify that my results below are (in)valid.

Thanks.

Message: 11110101 11110101
Polynomial: X4 + x2 + 1
Divisor (Derived from polynomial): 10101
Remainder:111
Result: There is an error in the above message?

Also, I had a link to an online calculator that would do the division but can't relocate it, any links to a calculator would be greatly appreciated.

Thanks.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted
 1111010111110101 | 10101
+10101            | 11001011101
  10111           |
 +10101           |
     10011        |
    +10101        |
       11011      |
      +10101      |
        11101     |
       +10101     |
         10000    |
        +10101    |
           10110  |
          +10101  |
              111 | <- you are right! there is an error in the message!
share|improve this answer
add comment

Mathematica gave me the same result:

În[1]:=s=x^7+x^6+x^5+x^4+x^2+1;

In[2]:=PolynomialRemainder[(1+x^8)s, 1+x^2+x^4,x]

Out[2]:= 1+x+x^2

So there wasn't even any need to reduce the coefficients modulo two in the end. I don't know whether Wolfram Alpha supports this. Anyway, you got it right.

In this case we can also find non-divisibility by observing that $$ \begin{aligned}s&=x^7+x^6+x^5+x^4+x^2+1=(x^2+x+1)x^5+(x^2+x+1)^2\\ &=(x^2+x+1)(x^5+x^2+x+1)=(x^2+x+1)(x+1)^2(x^3+x+1)\end{aligned}$$ implying that your message polynomial $$ m=(x^8+1)s=(x^2+x+1)(x^3+x+1)(x+1)^{10} $$ is not divisible by $x^4+x^2+1=(x^2+x+1)^2$. In general trying to factor the message polynomial is a very bad idea, though :-)

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.