The cyclic redundancy check (CRC) is based on division in the ring of polynomials over the finite field GF(2) (integers modulo 2): coefficients are 0 or 1 and arithmetic is performed modulo 2. Any string of bits can be interpreted as the coefficients of a message polynomial M(x). To compute the CRC, multiply M(x) by x^n, where n is the degree of the generator polynomial G(x), and then divide x^nM(x) by G(x). The remainder R(x) of this Euclidean division, with degree strictly less than n, has coefficients that form the CRC bits; the quotient is not used. Equivalently, R(x) = x^nM(x) mod G(x), and the transmitted codeword is T(x) = x^nM(x) + R(x), which is divisible by G(x). On reception, the receiver either separates M and R and recomputes R to compare with the received R, or checks that the received codeword is divisible by G(x); if the remainders match (or the remainder is zero), the receiver assumes the message is correct. In practice, CRC calculations most closely resemble long division in binary, except that the subtractions involved do not borrow from more significant digits and thus become exclusive-or operations. A CRC is a checksum in a strict mathematical sense, as it can be expressed as the weighted modulo-2 sum of per-bit syndromes, but that term is generally reserved for sums computed using larger moduli such as 10, 256, or 65535. CRCs can also be used as part of error-correcting codes, which allow not only the detection of transmission errors but also the reconstruction of the correct message. These codes are based on closely related mathematical principles.

Polynomial arithmetic modulo 2

Since the coefficients are constrained to a single bit, any arithmetic operation on CRC polynomials must map the result’s coefficients to either zero or one. In addition, coefficients are added modulo 2, so polynomial addition modulo 2 is the same as bitwise XOR. Since XOR is its own inverse, polynomial subtraction modulo 2 is also the same as bitwise XOR. Multiplication is similar (a carry-less product). We can also divide polynomials modulo 2 and find the quotient and remainder; the remainder is used in CRC calculations. In the above equations, M(x) represents the original message bits, G(x) is the generator polynomial, and the remainder R(x) is the CRC. If the degree of the generator polynomial is r, we first multiply the message polynomial by x^r to append r zeros. 

Variations: There are several standard variations on CRCs, any or all of which may be used with any CRC polynomial. Implementation variations such as endianness and CRC presentation only affect the mapping of bit strings to the coefficients of M(x) and G(x) and do not change the algorithm's properties. 

To check the CRC, instead of calculating the CRC on the message and comparing it to the transmitted CRC, a CRC calculation may be run on the entire codeword. If the result (called the residual) is zero, the check passes. This works because the codeword is divisible by G(x). This simplifies many implementations by avoiding the need to treat the last few bytes of the message specially when checking CRCs. 

The shift register may be initialized with ones instead of zeros. This is equivalent to inverting the first r bits of the message before feeding them into the algorithm. The CRC equation becomes M(x)x^r + R(x) ≡ 0 (mod G(x)), where r is the length of the CRC in bits. The change this imposes on R(x) is a function of the generating polynomial and the message length. This method is used because an unmodified CRC does not distinguish between two messages that differ only in the number of leading zeros, since leading zeros do not affect the value of M(x). When this inversion is done, the CRC does distinguish between such messages. The CRC may be inverted before being appended to the message stream. While an unmodified CRC distinguishes between messages with different numbers of trailing zeroes, it does not detect trailing zeroes appended after the CRC remainder itself. This is because all valid codewords are multiples of the generator polynomial, so any multiple of a valid codeword is also a multiple. (In fact, this is precisely why the first variant described above works.) In practice, the last two variations are almost always used together. They change the transmitted CRC, so they must be implemented at both the transmitter and the receiver. While presetting the shift register to ones is straightforward to do at both ends, inverting affects receivers implementing the first variation, because the CRC of a full codeword that already includes a CRC is no longer zero. Instead, it is a fixed non-zero pattern: the CRC of the inversion pattern of ones. The CRC may thus be checked either by the obvious method of computing the CRC on the message, inverting it, and comparing the result with the CRC in the message stream, or by calculating the CRC on the entire codeword and comparing it with an expected fixed value, called the check polynomial, residue, or magic number. This value may be computed directly, or equivalently by computing the unmodified CRC of a message consisting of all ones. These inversions are very common but not universally performed, even for CRC-32 and CRC-16-CCITT.