# Why is the CRC, essentially polynomial division over GF(2), linear?

On the Wikipedia page for Cyclic Redundancy Check, it says that:

CRC is a linear function with a property that $\operatorname {crc} (x\oplus y)=\operatorname {crc} (x)\oplus \operatorname {crc} (y)$

This linearity property is a vital part of what makes CRC implementations efficient, and so I would like to understand how this conclusion was derived.

On the related page on CRC mathematics, the CRC is defined as $R(x)$ where:

$$\begin{eqnarray}M(x)\cdot x^{n} &=& Q(x)\cdot G(x)+R(x) \\ R(x) &=& M(x)\cdot x^{n}\,{\bmod \,}G(x)\\ \end{eqnarray}$$

How does one get from this to the linearity conclusion?

As a clarification, let's disregard the complicating issues of actual CRC standards like the non-zero initial values, bit inversions and endianness. Just the polynomial division.

## 2 Answers

The basic tool being used here is polynomial division: if $f(x)$ and $g(x)$ are polynomials with coefficients in some field $K$, then there are unique polynomials $q(x)$ and $r(x)$ such that: $$f(x) = q(x)\cdot g(x) + r(x)$$ where either $r = 0$ or $\deg(r) < \deg(q)$. In the CRC algorithm, $K$ is the field $\Bbb{Z}_2$ with two elements, $g = G$ is some fixed polynomial, $f$ is the polynomial whose coefficients are the bits of the message padded with $\deg(g)$ zeroes and the CRC comprises the bits given by the coefficients of $r$.

The linearity property is a property of polynomial division: if you fix the divisor $g$, then the remainder $r$ is a linear function of $f$. I am not aware that this has anything to do with the efficiency of implementing the CRC algorithm (I thought it was usually implemented by the usual polynomial long division algorithm).

With $G(x)$ fixed, if you have two messages $M_1$ and $M_2$ then

$$\begin{eqnarray}M_1(x)\cdot x^{n} &=& Q_1(x)\cdot G(x)+R_1(x) \\ M_2(x)\cdot x^{n} &=& Q_2(x)\cdot G(x)+R_2(x)\\ \end{eqnarray}$$

where $R_1$ and $R_2$ are the respective CRC of $M_1$ and $M_2$.

If you want to compute the CRC of $M = M_1 \oplus M_2$, the XOR of $M_1$ and $M_2$, you have to

$$\begin{eqnarray}M(x) \cdot x^n = \mbox{ (in \mathbb{F}_2[x])  }&=&(M_1(x) + M_2(x))\cdot x^{n}\\ &=& Q_1(x)\cdot G(x)+Q_2(x)\cdot G(x)+R_1(x)+R_2(x) \\ \end{eqnarray}$$

Then the CRC of $M$ is $R_1(x)+R_2(x)$ that, in $\mathbb{F}_2[x]$, is $R_1(x)\oplus R_2(x)$, the XOR between both CRCs.