Mathematics of cyclic redundancy checks

The cyclic redundancy check (CRC) is based on division in the ring of polynomials over the finite field GF(2) (the integers modulo 2), that is, the set of polynomials where each coefficient is either zero or one, and arithmetic operations wrap around.

Any string of bits can be interpreted as the coefficients of a message polynomial of this sort, and to find the CRC, we multiply the message polynomial by ${\displaystyle x^{n}}$ and then find the remainder when dividing by the degree-${\displaystyle n}$ generator polynomial. The coefficients of the remainder polynomial are the bits of the CRC.

In general, computation of CRC corresponds to Euclidean division of polynomials over GF(2):

Here ${\displaystyle M(x)}$ is the original message polynomial and ${\displaystyle G(x)}$ is the degree-${\displaystyle n}$ generator polynomial. The bits of ${\displaystyle M(x)\cdot x^{n}}$ are the original message with ${\displaystyle n}$ zeroes added at the end. The CRC 'checksum' is formed by the coefficients of the remainder polynomial ${\displaystyle R(x)}$ whose degree is strictly less than ${\displaystyle n}$. The quotient polynomial ${\displaystyle Q(x)}$ is of no interest. Using modulo operation, it can be stated that

...
Wikipedia