4
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What does the notation $GF(2^{32})^\times$ mean? $\endgroup$ – Gilles 'SO- stop being evil' Nov 28 '13 at 11:06
  • $\begingroup$ The multiplicative group of the field. $\endgroup$ – Yuval Filmus Nov 28 '13 at 16:56
  • $\begingroup$ 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?). $\endgroup$ – Gilles 'SO- stop being evil' Nov 28 '13 at 17:00
  • $\begingroup$ Zero is not out of range - you can get zero with a zero message. There are also other ways to get zero. See my addendum. $\endgroup$ – Yuval Filmus Dec 1 '13 at 1:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Luis Colorado Apr 12 '18 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.