Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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). –  Qiaochu Yuan Aug 25 '11 at 0:01
2  
@Qiaochu: you should make that an answer! –  Mariano Suárez-Alvarez Aug 25 '11 at 2:28
1  
@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. –  Qiaochu Yuan Aug 25 '11 at 2:35
4  
@Qiaochu, go on, be brave! Worst comes to worst, OP explains "other issue", you can always delete/amend your answer. –  Gerry Myerson Aug 25 '11 at 4:22

1 Answer 1

up vote 5 down vote accepted

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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