debugMinor
Range of CRC-32
Viewed 0 times
rangecrcstackoverflow
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#18431, answer score: 6
Revisions (0)
No revisions yet.