# Range of CRC-32

What is the range of “the” CRC-32, the one used by Unix, Ethernet, zip, and many other industrial standards?

Mathematically, a CRC is defined as follows: let $G$ be the CRC polynomial in $\mathbb{F}_2[X]$, and $M$ be a representation of the input bitstring in $\mathbb{F}_2[X]$. Let $Q$ be the quotient of $M \cdot X^{\deg G}$ by $G$; the CRC value is $\bar Q(2)$ where $\bar Q$ is the canonical injection of $Q$ into $\mathbb{Z}[X]$. The codomain of the CRC function is thus the integer range $[0,2^{\deg G}-1]$ (or equivalently the set of polynomials of degree $\le \deg G$). Which values are reachable?

This question is specifically about $$G = G_\text{Ethernet} = X^{32}+X^{26}+X^{23}+X^{22}+X^{16}+X^{12}+X^{11}+X^{10}+X^{8}+X^{7}+X^{5}+X^{4}+X^{2}+X^{1}+X^{0}$$ though I'm curious whether the result generalizes to other common CRC.

Bonus: is there anything known and interesting about the relative density of preimages?

The CRC polynomial is very probably primitive, that is the order of $X$ modulo $G$ is $2^{32}-1$. In other words, $X$ is a generator of $GF(2^{32})^\times$. So using inputs $0,2^0,\ldots,2^{2^{32}-2}$ will result in all possible $2^{32}$ values.
CRCs are hopefully always chosen with primitive polynomials, so this result is general. Even if the polynomial is irreducible but not primitive, you can always pick some generator $Q(X)$ of $GF(2^{32})^\times$ and use it to obtain the same result.
Addendum: if $CRC(M_1) = CRC(M_2)$ then $M_1-M_2$ is a multiple of the generating polynomial. Hence CRC is a bijection from the set of messages of length $4$ bytes to integers of length 32 bits.
• What does the notation $GF(2^{32})^\times$ mean? – Gilles 'SO- stop being evil' Nov 28 '13 at 11:06
• Ah, I see. So there are $2^{32}-1$ (not $2^{32}$) possible values, right? With $0$ being out of range (is there an obvious reason for that?). – Gilles 'SO- stop being evil' Nov 28 '13 at 17:00
• @YuvalFilmus, being primitive is not necessary to demonstrate that the set of possible remainders is indeed $2^{32}$. being primitive only proves that the powers of any of the $2^{32}$ values cycle on the whole set of values $1\dots 2^{32} - 1$ but any of the $2^{32}$ values, when divided by the generator polynomial gives itself... as when using $GF(N)$ and calculating the modulus of any of the residuous mod N with the modulus... the operation is idempotent. – Luis Colorado Apr 12 '18 at 9:33