Irreducible polynomial over finite field

  • Thread starter Zoe-b
  • Start date
  • #1
98
0

Homework Statement


Factor x^16-x over the fields F4 and F8

Homework Equations


factored over Z (or Q), x^16-x = (x*(x - 1)*(x^2 + x + 1)*(x^4 + x^3 + x^2 + x + 1)*(x^8 - x^7 + x^5 - x^4 + x^3 - x + 1)


The Attempt at a Solution



I know the that quadratic and higher terms I have left do not have any linear factors.. I'm obviously missing something. But even with that I'm not really sure how to start checking- I *think* I'm right in saying I can check for irreducibility over F2 first, because that would be implied by irreducibility over the larger field. Then there are less polynomials to check, but still a fair few for the term of degree 8..

Thanks in advance :)
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
Try factoring over F16 first. :smile:
 
  • #3
98
0
Ok.. so x^16-x splits completely over F(16) because the non-zero elements form a multiplicative group and each element a satisfies a^16= a
My problem now is that I really have very little concept of how the fields F(16) and F(8) are related to each other- for a while after starting this question I was thinking of them as being integers modulo 16 (or 8 respectively) but this is clearly wrong. How can I factor it into something with coefficients in F(4) without knowing how the elements of F(4) interact...?
 
  • #4
I like Serena
Homework Helper
6,579
176
As far as I can tell F8 and F16 are unrelated.
That is, there is no homomorphism that maps one onto another, since the orders of the respective multiplicative groups do not divide each other (being respectively 7 and 15).

So I'm very interested in what Hurkyl intended.


I was able to factorize the 8th degree polynomial into 4th degree polynomials by setting (in either F4[x] or F8[x]):
$$x^8 - x^7 + x^5 - x^4 + x^3 - x + 1 = (x^4 + ax^3 + bx^2 + cx + 1)(x^4 + (a+1)x^3 + b^{-1} x^2 + (c+1)x + 1)$$

This is solvable in F4 and also in F8.
After that I could repeat the process with 2nd degree polynomials (with the last coefficient unequal to 1 btw).
 
  • #5
98
0
Well F(16) is useful for F(4)- I think because 4=2^2 , 16= 2^4 and 2 divides 4. Clearly 3 does not divide 4 so I'm struggling to see the relevance to F(8). I've now done it (I think!) for F(4), the polynomial splits completely into linear factors, each repeated 4 times. These are precisely the roots of x^4 - x, but (x^4-x)^4 gives x^16-x. This is dependant on being able to equate x^4 with x in F(4) but I think this is valid since every element of F(4) satisfies this equation.

F(8) has no linear factors other than 0,1 though so still a bit stuck..
 
  • #6
I like Serena
Homework Helper
6,579
176
I just checked and I can find no mapping of F16 to F4 that retains the field structure (adding as well as multiplication), so I do not see how factorization in F16 would help.
 
  • #7
98
0
Its not a mapping- F(4) is contained within F(16), no?
 
  • #8
I like Serena
Homework Helper
6,579
176
The elements are contained, but the multiplication and addition tables are different.
 
  • #9
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
I Like Serena: The subset of [itex]\mathbb{F}_{16}[/itex] of solutions to [itex]x^4 - x[/itex] form a subfield of [itex]\mathbb{F}_{16}[/itex]. Since it has 4 elements it must be (isomorphic to) [itex]\mathbb{F}_{4}[/itex]. In the language of Galois theory, [itex]x \mapsto x^4[/itex] is a field automorphism of [itex]\mathbb{F}_{16}[/itex]. [itex]\mathbb{F}_{4}[/itex] is (isomorphic) to its fixed field.

If [itex]\alpha[/itex] and [itex]\beta[/itex] are primitive elements (over [itex]\mathbb{F}_{2}[/itex]) of [itex]\mathbb{F}_{4}[/itex] and [itex]\mathbb{F}_{16}[/itex], then send [itex]\alpha \mapsto \beta^5[/itex] (or to [itex]\beta^{10}[/itex])



My problem now is that I really have very little concept of how the fields F(16) and F(8) are related to each other-
They don't much.

[itex]\mathbb{F}_{16}[/itex] consists of 2 elements of degree 1, 2 elements of degree 2, and 12 elements of degree 4 (over [itex]\mathbb{F}_{2}[/itex].

[itex]\mathbb{F}_{8}[/itex] consists of 2 elements of degree 1 and 6 elements of degree 3.

How do I know these facts? Because I know all of their subfields. The calculation would be a little more involved for, say, [itex]\mathbb{F}_{64}[/itex], but still a straightforward combinatorial exercise.


Since gcd(3,4) = 1, every element of [itex]\mathbb{F}_{16}[/itex] of degree 4 over [itex]\mathbb{F}_{2}[/itex] must also be degree 4 over [itex]\mathbb{F}_{8}[/itex]. (of course, that same element would be degree 2 over [itex]\mathbb{F}_{4}[/itex])


There are various equivalent descriptions of [itex]\alpha[/itex] being degree n over [itex]\mathbb{F}_{q}[/itex]:
  • [itex]\mathbb{F}_{q}(\alpha) \cong \mathbb{F}_{q^n}[/itex]
  • The minimal polynomial of [itex]\alpha[/itex] over [itex]\mathbb{F}_{q}[/itex] has degree n
  • The orbit of [itex]\alpha[/itex] under [itex]x \mapsto x^q[/itex] (i.e. the set [itex]\{ \alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}, \cdots \}[/itex]) has n elements. (and these are the roots of the aforementioned minimal polynomial)


Just knowing the degrees of the roots (and that they're distinct) over [itex]\mathbb{F}_2[/itex] tells me that the irreducible factorization (over [itex]\mathbb{F}_2[/itex]) is
[itex]x^{16} - x[/itex] = <linear> <linear> <quadratic> <quartic> <quartic> <quartic>​
In fact, if I have a model of [itex]\mathbb{F}_{16}[/itex] and know an algorithm for computing minimal polynomials, I could use it to actually compute the factors.
 
Last edited:
  • #10
I like Serena
Homework Helper
6,579
176
I Like Serena: The subset of [itex]\mathbb{F}_{16}[/itex] of solutions to [itex]x^4 - x[/itex] form a subfield of [itex]\mathbb{F}_{16}[/itex]. Since it has 4 elements it must be (isomorphic to) [itex]\mathbb{F}_{4}[/itex]. In the language of Galois theory, [itex]x \mapsto x^4[/itex] is a field automorphism of [itex]\mathbb{F}_{16}[/itex]. [itex]\mathbb{F}_{4}[/itex] is (isomorphic) to its fixed field.

If [itex]\alpha[/itex] and [itex]\beta[/itex] are primitive elements (over [itex]\mathbb{F}_{2}[/itex]) of [itex]\mathbb{F}_{4}[/itex] and [itex]\mathbb{F}_{16}[/itex], then send [itex]\alpha \mapsto \beta^5[/itex] (or to [itex]\beta^{10}[/itex])

I see! :)
A subfield.

So we can factorize ##x^{16}-x## into first degree polynomials with each of the elements of F16.
And by selecting smart combinations of 2 factors, we can find quadratic ones in F4.
Nice!

But if I see it correctly, this does not work with F8.
F16 does not seem to have a subfield that is isomorphic with F8.


[itex]\mathbb{F}_{16}[/itex] consists of 2 elements of degree 1, 2 elements of degree 2, and 12 elements of degree 4 (over [itex]\mathbb{F}_{2}[/itex].

[itex]\mathbb{F}_{8}[/itex] consists of 2 elements of degree 1 and 6 elements of degree 3.

This I don't get.

I thought the multiplicative degrees of the 2 non-identity elements in F4 would be 3.
In F8 the (multiplicative) degrees of the 6 non-identity elements would be 7.
And F16 would have 2 elements of order 3, 4 elements of order 5, and 8 elements of order 15.

The additive degrees of all non-identity elements would be 2 in each of the fields.

How are you counting this?
 
  • #11
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
How are you counting this?
I did give a list of things equivalent to what I mean by degree. :tongue:

(p.s. I've never heard the concept you described called "degree". I usually hear it called the "order" of an (group) element)

(p.p.s. if you need to think in terms of subfields, you can use [itex]\mathbb{F}_{2^{12}}[/itex], which contains both [itex]\mathbb{F}_{8}[/itex] and [itex]\mathbb{F}_{16}[/itex])
 
  • #12
I like Serena
Homework Helper
6,579
176
I did give a list of things equivalent to what I mean by degree. :tongue:

(p.s. I've never heard the concept you described called "degree". I usually hear it called the "order" of an (group) element)

(p.p.s. if you need to think in terms of subfields, you can use [itex]\mathbb{F}_{2^{12}}[/itex], which contains both [itex]\mathbb{F}_{8}[/itex] and [itex]\mathbb{F}_{16}[/itex])

Yeah well, I did not understand everything you wrote, so I just started at the beginning.
And you caught me - English is not my native language and in my language there is no distinction between the words degree and order.

But what do you mean by degree then? Do you mean the degree of polynomials?

As I understand it F8 is isomorphic with ##(\mathbb{Z}/2\mathbb{Z})[T]/(T^3+T+1)##.
So its elements are ##\{0, 1, T, T^2, T+1, T^2+T, T^2+T+1, T^2+1\}##, which can also be written as ##\{0, 1, T, T^2, T^3, T^4, T^5, T^6\}##.
But the degrees of these polynomials do not appear to correspond to the degrees you mentioned.

I'm still not getting it. :cry:
 
  • #13
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
But what do you mean by degree then?

I mean

There are various equivalent descriptions of [itex]\alpha[/itex] being degree n over [itex]\mathbb{F}_{q}[/itex]:
  • [itex]\mathbb{F}_{q}(\alpha) \cong \mathbb{F}_{q^n}[/itex]
  • The minimal polynomial of [itex]\alpha[/itex] over [itex]\mathbb{F}_{q}[/itex] has degree n
  • The orbit of [itex]\alpha[/itex] under [itex]x \mapsto x^q[/itex] (i.e. the set [itex]\{ \alpha, \alpha^q, \alpha^{q^2}, \alpha^{q^3}, \cdots \}[/itex]) has n elements. (and these are the roots of the aforementioned minimal polynomial)
 

Related Threads on Irreducible polynomial over finite field

Replies
2
Views
5K
Replies
0
Views
894
Replies
3
Views
2K
Replies
6
Views
2K
Replies
2
Views
8K
Replies
17
Views
7K
  • Last Post
Replies
0
Views
2K
  • Last Post
Replies
1
Views
4K
  • Last Post
Replies
2
Views
855
Replies
5
Views
2K
Top