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