[Math] Primitive polynomial vs irreducible polynomial for construction field $GF(2)[x]/\langle p(x)\rangle$

coding-theoryfinite-fieldsirreducible-polynomials

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.

EDIT:

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?

Best Answer

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".

Related Question