Wednesday, June 5, 2019

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



Question 1: Can the field GF(2)[x]/p(x) 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(24), there are 3 irreducible polynomials of degree 4 in GF(2)[x], but one of them is not primitive:





  • p1(x)=x4+x+1 (irreducible AND primitive)

  • p2(x)=x4+x3+1 (irreducible AND primitive)

  • p3(x)=x4+x3+x2+x+1 (irreducible but NOT primitive)



Matlab, for example, refuses to "create" an element of such a field using the above p3(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 p3(x)=x4+x3+x2+x+1 (irreducible but NOT primitive) into GF(2)[x]/p3(x) results in a field, with various elements that are generators: x+1, x2+1, x2+x, x2+x+1, etc . For example g=x+1 is a generator of the multiplicative group, because the sequence g0,g1,...,g14 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 p3(x), and x0=x5=x10=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,} is cumbersome when compared with {x1,x2,}, 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:AB and I want to get bijection. Can I just resting codomain to f(A)? I know that every function i...