I understand the need for using an irreducible polynomial for a prime power finite field when doing multiplication with numbers in those fields. For certain applications, such as the Q parity bytes used in RAID6, a non-zero number should have a multiplicative inverse which might fail if it can be multiplied by another non-zero number in that field and yield zero. However, I don't fully understand its importance in its use with cyclic redundancy checks. This seems to be a bit different scenario because instead of working with numbers inside the field, your taking a message that represents a number that's generally much, much larger than the field and dividing it down to fit in the field. After that, your pretty close to been done with the CRC with maybe a an XOR to complete the job.
As a counter example, I discovered that the polynomial used for the CRC32 on CD-ROM is composed of two smaller polynomial: $(x^{16} + x^{15} + x^2 + 1) \cdot (x^{16} + x^2 + x + 1)$.
Maybe the a question I need to ask is a why would they use a reducible polynomial in this case rather than a known irreducible one?
Best Answer
Say you want to transmit a polynomial $M(x)$, but the recipient receives a slightly different polynomial $M'(x)$. We can define the "error polynomial":
$$E(x)=M'(x)-M(x)$$
Call the CRC-polyomial $P$. Then an error will go undetected iff $P$ divides $E$, or in other words if every divisor of $P$ is also a divisor of $E$. We can therefore guarantee that certain kinds of errors get caught by analysing the divisors of $P$ and $E$. Here are a few simple examples:
$E(x)=x^{n+m}+x^{n+m-1}+...+x^n=x^n(x^m+x^{m-1}+...+1)$, a burst error, ie. $m+1$ flipped bits in a row. This will be caught if $P$ has nonzero constant term (so it has no common divisors with $x^n$) and is of degree greater than $m$ (since it then cannot divide a polynomial of degree $m$).
$E(1)=1$, ie. an odd number of flipped bits. This will be caught if $x+1$ divides $P(x)$, since then $P(1)=0$.
$E(x) = x^{n+m} + x^m=x^n(x^m+1)$, ie. two flipped bits $m$ bits appart. This will be caught if $P$ is a multiple of a primitive polynomial of order greater than $m$. So a primitive polynomial of degree $d$ will catch two errors if they are less than $2^d-1$ bits appart.
So in short, using a reducible polynomial may indeed be desirable if you want to guarantee certain kinds of errors get caught.