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?
Range of CRC-32
arithmetic;error correcting codes;crc
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.