1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Irreducible polynomial over finite field

  1. Feb 11, 2012 #1
    1. The problem statement, all variables and given/known data
    Factor x^16-x over the fields F4 and F8

    2. Relevant 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)


    3. 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 :)
     
  2. jcsd
  3. Feb 11, 2012 #2

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Try factoring over F16 first. :smile:
     
  4. Feb 11, 2012 #3
    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...?
     
  5. Feb 11, 2012 #4

    I like Serena

    User Avatar
    Homework Helper

    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).
     
  6. Feb 11, 2012 #5
    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..
     
  7. Feb 11, 2012 #6

    I like Serena

    User Avatar
    Homework Helper

    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.
     
  8. Feb 11, 2012 #7
    Its not a mapping- F(4) is contained within F(16), no?
     
  9. Feb 12, 2012 #8

    I like Serena

    User Avatar
    Homework Helper

    The elements are contained, but the multiplication and addition tables are different.
     
  10. Feb 12, 2012 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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])



    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: Feb 12, 2012
  11. Feb 12, 2012 #10

    I like Serena

    User Avatar
    Homework Helper

    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.


    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?
     
  12. Feb 12, 2012 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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])
     
  13. Feb 12, 2012 #12

    I like Serena

    User Avatar
    Homework Helper

    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:
     
  14. Feb 12, 2012 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I mean

     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook