Question 1: Can the field $GF(2)[x]/\langle p(x)\rangle$ be constructed using $p(x)$ irreducible but NOT primitive? what are the consequences?

In my readings, the math books talk about irreducible polynomial to construct a field, but in other literature for error correction codes they say that we use primitive polynomial instead.

For example, to construct the field $GF(2^4)$, there are 3 irreducible polynomials of degree 4 in $GF(2)[x]$, but one of them is not primitive:

  • $p_1(x)=x^4 + x + 1$ (irreducible AND primitive)
  • $p_2(x)=x^4 + x^3 + 1$ (irreducible AND primitive)
  • $p_3(x)=x^4 + x^3 + x^2 + x + 1$ (irreducible but NOT primitive)

Matlab, for example, refuses to "create" an element of such a field using the above $p_3(x)$ polynomial:

>> a=gf(15, 4, 'x^4 + x^3 + x^2 + x + 1')
Error using gf (line 96)
PRIM_POLY must be a primitive polynomial.


I've found that using $p_3(x)=x^4+x^3+x^2+x+1$ (irreducible but NOT primitive) into $GF(2)[x]/\langle p_3(x) \rangle$ results in a field, with various elements that are generators: $x+1$, $x^2+1$, $x^2+x$, $x^2+x+1$, etc . For example $g=x+1$ is a generator of the multiplicative group, because the sequence $g^0, g^1, ..., g^{14}$ generates every element of this field, and multiplication using sum of exponents works. One curious point is that $x$ is not a generator of this field using $p_3(x)$, and $x^0=x^5=x^{10}=1$ (there are repetitions).

Then I've learned that irreducible poly is mandatory to make this a field, but primitive is an extra just to make exponentials prettier. For example, the sequence of powers for the generator $x+1$: $\{(x+1)^1, (x+1)^2, \dots\}$ is cumbersome when compared with $\{x^1, x^2, \dots\}$, then it is conveninent to have $x$ as a generator element.

Question 2: I'm correct about this?

  • $\begingroup$ What is the definition of primitive here? $\endgroup$ – carmichael561 Aug 16 '17 at 5:06
  • $\begingroup$ @carmichael561, primitive poly in $GF(2)[x]$ are those irreducible polynomials of degree $m$ that divides $a(x)=x^n+1$, where $n=2^m-1$, but not divides any such $a(x)$ with smaller $n$. $\endgroup$ – Berk7871 Aug 16 '17 at 5:11
  • 2
    $\begingroup$ Use something better than MATLAB! $\endgroup$ – Lord Shark the Unknown Aug 16 '17 at 5:14
  • $\begingroup$ Here we explained some points that you may find interesting. My semi-educated guess is that Matlab's restriction is related to either the 1st point in my answer or some consequences related to it. Getting to use efficient algorithms based on the discrete Fourier transformation for some purpose? Or some such gadgets? Those are frequently needed in coding theoretical applications. Telcomm industry is one of the heavy users of Matlab, so... $\endgroup$ – Jyrki Lahtonen Aug 16 '17 at 6:07
  • $\begingroup$ @carmichael561 I added an explanation to the tag wiki because the question/confusion comes up frequently enough. $\endgroup$ – Jyrki Lahtonen Aug 16 '17 at 6:17

You only need an irreducible polynomial to construct a galois field in this way.

The only thing selecting a primitive polynomial does is force (the congruence class of) $x$ to be a generator of the multiplicative group. In fact, this is the definition of "primitive".

  • $\begingroup$ may you appreciate my 2nd question, please? $\endgroup$ – Berk7871 Aug 18 '17 at 3:48

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.