Relating factors of a polynomial over GF(q) and G F ( q m </msup> ) I am rea

Eve Dunn

Eve Dunn

Answered question

2022-05-16

Relating factors of a polynomial over GF(q) and G F ( q m )
I am reading Richard Blahut's book "Algebraic Codes for Data Transmission" and have come to an impasse in my understanding in section 5.3. In this section, the author wants to relate the factors of a polynomial over GF(q) and the factors of that same polynomial over a GF-extension field G F ( q m ).
There is a good example in the book that I will use here to ask my question. Specifically the GF fields in this example use q=2 and m=4, so there is the prime field GF(2) and the extension field G F ( 2 4 ). The polynomial to be factored over both of these fields is one with particularly special properties, of the form x q m 1 1. So, the polynomial for this example is x 15 1.
The author first factors x 15 1 over GF(2). The prime factors are:
x 15 1 = ( x + 1 ) ( x 2 + x + 1 ) ( x 4 + x + 1 ) ( x 4 + x 3 + 1 ) ( x 4 + x 3 + x 2 + x + 1 )
This factorization over GF(2) makes sense to me and I can easily verify it in MATLAB.
The author then chooses two of the above prime factors and forms a new polynomial:
g ( x ) = ( x 4 + x 3 + 1 ) ( x 4 + x 3 + x 2 + x + 1 ) = x 8 + x 4 + x 2 + x + 1
The above multiplication over GF(2) also makes sense to me and I can easily verify it in MATLAB.
However, the author then changes to analyzing the same polynomial g ( x ) = x 8 + x 4 + x 2 + x + 1 in the extension field G F ( 2 4 ). It seems to be implied that because G F ( 2 4 ) in an extension field of GF(2), and because the polynomial in question is comprised of prime factors (over GF(2)) of the special composite polynomial x15−1, that this switch to the extension field G F ( 2 4 ) is justified.
To analyze g ( x ) in the extension field, we agree to represent the 16 elements of the extension field as the usual powers of the primitive field element alpha:
0 , 1 , α , α 2 , α 3 , α 4 , α 5 , α 6 , α 7 , α 8 , α 9 , α 10 , α 11 , α 12 , α 13 , α 14
The author claims that the aforementioned polynomial g ( x ) = x 8 + x 4 + x 2 + x + 1 has roots/zeroes over
g ( α 3 ) = 0
I am completely unable to make sense of this claim. It raises numerous questions in my mind, and the most basic of these questions is, how can I verify that g ( α ) = 0 and that g ( α 3 ) = 0?
To show how I've tried to verify that g ( α ) = 0 for g ( x ) = x 8 + x 4 + x 2 + x + 1, the author uses the following detailed representation of the elements of extension field G F ( 2 4 ). Of course to describe the elements of any GF extension field, we must choose an irreducible polynomial for the reducing modulus, and throughout the book the author uses the modulus α 4 + α + 1, yielding the 16 field elements:
0 = α 1 = α 0 α 1 = α α 2 = α 2 α 3 = α 3 α 4 = α + 1 α 5 = α 2 + α α 6 = α 3 + α 2 α 7 = α 3 + α + 1 α 8 = α 2 + 1 α 9 = α 3 + α α 10 = α 2 + α + 1 α 11 = α 3 + α 2 + α α 12 = α 3 + α 2 + α + 1 α 13 = α 3 + α 2 + 1 α 14 = α 3 + 1
Given the above element representation of G F ( 2 4 ), we return to the enigmatic claim that for g(x)=x8+x4+x2+x+1, there is the root g(α)=0 over GF(24). We have:
g ( x ) = x 8 + x 4 + x 2 + x + 1
So it seems that for g(x)=x8+x4+x2+x+1 polynomial, g ( α ) 0.
Can anyone show me how to demonstrate that α (as a GF(16) element) is a root of a polynomial that was computed over GF(2)?
If it would be helpful, I can scan the 3 pages of the book and you can see the author's own words for the above ideas. He throws this information at you very quickly, so it's fairly difficult for me (as a non-mathematician) to follow.

Answer & Explanation

Abigailf91er

Abigailf91er

Beginner2022-05-17Added 13 answers

It’s really difficult to see what your author was trying to get at here. In this particular example, where the polynomial is X 15 1 over k=GF(2), the way it factors over K=GF(16) is that it splits completely into linear factors, ’cause the elements of K are exactly the roots of X 16 X.
He has factored X 15 1 over GF(2) correctly: the linear factors account for the elements of GF(2), the quadratic factor accounts for the two additional elements of GF(4), and the three quartic factors account for the twelve additional elements of GF(16). You’ve used one of these quartics, the last one, X 4 + X + 1 = f ( X ), for constructing your GF(16), and we have 0 = f ( α ) = f ( α 2 ) = f ( α 4 ) = f ( α 8 ), ’cause any time β is a root of a GF(2) polynomial h(X), β 2 will also be a root of h.
His g is product of the other two quartics you’ve written down, namely X 4 + X 3 + 1 and X 4 + X 3 + X 2 + X + 1. It follows that every element of K that’s neither in GF(4) nor a root of f will be a root of g. Since the elements of GF(4) are 0, 1, α 5 = α + α 2 , and α 10 = 1 + α + α 2 , the roots of g should be { α 3 , α 6 , α 7 , α 9 , α 11 , α 12 , α 13 , α 14 }, of which there are fortunately eight.
I don’t know whether this will help your understanding, nor whether it will explain what your author was trying to convey. If you have questions, I can try to answer them in an addendum.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?