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?

  • 5
    $\begingroup$ The difference is that the polynomial variable $x$ is not guaranteed to be a generator of the multiplicative group unless the polynomial is primitive. This is the definition of primitivity (in this context). $\endgroup$ – Qiaochu Yuan Aug 25 '11 at 0:01
  • 2
    $\begingroup$ @Qiaochu: you should make that an answer! $\endgroup$ – Mariano Suárez-Álvarez Aug 25 '11 at 2:28
  • 1
    $\begingroup$ @Mariano: well, I am not sure where the OP's confusion is. Ordinarily I would not consider a statement of a definition used in the question to be a helpful answer, so perhaps the OP is using a nonstandard definition or some other issue exists that I haven't picked up on. $\endgroup$ – Qiaochu Yuan Aug 25 '11 at 2:35
  • 4
    $\begingroup$ @Qiaochu, go on, be brave! Worst comes to worst, OP explains "other issue", you can always delete/amend your answer. $\endgroup$ – Gerry Myerson Aug 25 '11 at 4:22

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.
  • $\begingroup$ For an interesting variant about the structure of a discrete log table see this answer by @DilipSarwate. $\endgroup$ – Jyrki Lahtonen Oct 9 '11 at 7:01
  • $\begingroup$ And for the details of CRC calculation see this answer, again by Dilip. $\endgroup$ – Jyrki Lahtonen Feb 17 '12 at 4:49

A more intuitive way of understanding why reducing modulo a primitive irreducible polynomial is because you want to avoid duplicated values so that you get a full range field, as explained here:

Reed Solomon codes are created by the manipulation of finite group of numbers called a Galois Field. GF(256) is a field consisting of the every integer in the range 0 to 255 arranged in a particular order. If you could devise an arithmetic where the result of each operation produces another number in the field the overflow issues could be avoided. The generation (ordering) of the field is key. e.g. a simple monotonic series from 0 to 255 is a finite field BUT modulo 255 arithmetic fails commutative tests i.e. certain operations will not reverse.

A Galois field gf(p) is the element 0 followed by the (p-1) succeeding powers of α : 1, α, α^2, α^3, ..., α^(p-1)

Extending the gf(2) field used in binary arithmetic (and CRC calculation) to 256 elements that fit nicely in a computer byte: gf(2^8) = gf(256). Substituting the primitive element α=2 in the galois field it becomes 0, 1, 2, 4, 8, 16, and so on. This series is straightforward until elements greater than 127 are created. Doubling element values 128, 129, ..., 254 will violate the range by producing a result greater than 255. Some way must be devised to "fold" the results back into the finite field range without duplicating existing elements (this lets modulo 255 aritmetic out). This requires an irreducible primitive polynomial. "Irreducible" means it cannot be factored into smaller polynomials over the field. Without this mathematical insight it is possible to search for suitable numbers using empirical methods. There has to be some way of turning off bit 8 so an XOR operation on results greater than 255 with a number in the range 256 to 256+255 will find "irreducible primitive polynomial" if they exist. A "brute force" scanning program [source] checks each candidate and rejects potential polynomials if they duplicate existing elements in the field.

In other words: you need to reduce modulo a primitive irreducible polynomial to avoid duplicated values in your precomputed tables: indeed, your precomputed tables replace 0,1,2,...,256 by alpha^0, alpha^1, ..., alpha^255 so that you can easily replace multiplication by additions of exponents. However, you of course know that some values, like alpha^255, will overflow, so that you need to reduce modulo something. But if you don't use a primitive irreducible polynomial, you will get duplicated values, so that for example alpha^128 may be equal to alpha^1, thus giving you a truncated field (ie, not all values are uniquely represented).


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.