# Is this CRC calculation correct?

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.

-

 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!

-

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

-