What happens when you mod out by a non-primitive irreducible polynomial over $F_q$?

Question

What is the difference between modding out by a primitive polynomial and modding out by a non-primitive irreducible polynomial in a finite field $F_q$?

From what I understand either one should generate a field of $q^n$ elements, where $n$ is the degree of the polynomial, but a big deal is made out of finding primitive polynomials to make the larger field. What is the difference exactly in the way the resulting field works?

Answer 1

Qiaochu's comment contains the essential algebraic reason. I don't want to hog his priority, but as examples explaining why we are interested in primitive polynomials let me list the following:

1. Discrete log-tables. One efficient way of presenting a finite field in a computer program is to have a look-up table of discrete logarithms at hand. Using such a LUT implementing multiplication of two field elements becomes easy. At least every program involving finite fields that I have ever written begins by generating such a discrete logarithm table. To that end it is imperative to have a primitive polynomial $p(x)$. If you have one, then its easy to recursively present the powers of the generator $x+(p(x))$ as low degree polynomials in $x$, and you can generate the log-table while doing that.
2. As a concrete application, where we immediately see a primitive polynomial show an advantage I mention CRC-(=cyclic redundancy check) polynomials. These are polynomials in $F_2[D]$ (telecommunication engineers prefer to use $D$ as unknown here). The way these are used is that data to be protected by a CRC is first turned into a polynomial in $F_2[D]$ bit-by-bit. Then a few (redundancy) bits are appended to it so that in the end the resulting polynomial becomes divisible by a pre-determined CRC-polynomial $p(D)$. The point of the exercise is that whoever later reads the data can obtain a degree of confidence on its correctness by verifying that the data is, indeed, divisible by $p(D)$. What kind of errors might happen? Usually only a few bits will get toggled. If only a single bit is read incorrectly, then almost any $p(D)$ will work (as long as it is not a monomial). What about the occasions where two bits are toggled, say at positions $i$ and $j$? This would pass the CRC-test undetected only, if the binomial $D^i+D^j$ is divisible by $p(D)$. How does primitivity enter the scene? It is an easy exercise to show that any polynomial of $F_2[D]$ divides some binomials. The key question is: what's the degree of the lowest degree binomial divisible by $p(D)$? This is motivated by the fact the if we can maximize this degree, then we are maximizing the length of the data packet we can protect against such undetected errors. Because the number of redundant bits = the degree of $p(D)$, we are minimizing the nuymber of the redundancy bits needed to protect our data at this level of protection. W.l.o.g we can assume that $p(0)=1$, and then the we easily see that the lowest degree binomial divisible by $p(D)$ is $1+D^\ell$, where $\ell$ is the order of $D$ in the quotient ring $F_2[D]/p(D)$. So primitive polynomials show an advantage here. This is only the beginning of the theory, and occasionally we want to protect for more than two bit errors. A typical CRC-polynomial is of the form $p(D)=(1+D)q(D)$, where $q(D)$ is primitive. The extra factor $1+D$ has the effect that in order for an error to pass undetected, the number of errors must be even. Thus polynomials of the above form catch all the patterns of at most 3 errors up to a maximum size of data packet $2^{\deg q(D)}-1-\deg q(D)$ bits.