Wednesday, June 5, 2019

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



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?


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


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...