1
$\begingroup$

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.

2 Answers 2

2
 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!
1

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 :-)