Results 1 to 10 of 10

Math Help - How to determine coefficient in irreducible polynomial? HELP!!

  1. #1
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28

    How to determine coefficient in irreducible polynomial? HELP!!

    Here is my problem:

    Say if I have a irreducible polynomial for GF(2^2) that is x^2 + Nx + 1, (N = elements of GF(2)) how do I determine the possible values of N ? Given the irreducible polynomial for GF(2) is x^2 + x + 1

    thanks alot!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by classic_phohe View Post
    Here is my problem:

    Say if I have a irreducible polynomial for GF(2^2) that is x^2 + Nx + 1, (N = elements of GF(2)) how do I determine the possible values of N ? Given the irreducible polynomial for GF(2) is x^2 + x + 1

    thanks alot!
    Here is a field of order 4, F=\mathbb{Z}_2[t]/(t^2+t+1). Therefore, F = \{ 0,1,\alpha,\alpha+1\} where \alpha = t + (t^2+t+1) and \alpha^2 = \alpha + 1.

    For x^2 + Nx+1 to be irreducible it means it cannot have any zeros in F. The possible polynomials are: x^2+1,x^2+x+1,x^2+\alpha x+1, x^2+(\alpha+1)x+1. Which of these polynomials has zeros in F? The ones that do not are the irreducible ones.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28
    Quote Originally Posted by ThePerfectHacker View Post
    Here is a field of order 4, F=\mathbb{Z}_2[t]/(t^2+t+1). Therefore, F = \{ 0,1,\alpha,\alpha+1\} where \alpha = t + (t^2+t+1) and \alpha^2 = \alpha + 1.

    For x^2 + Nx+1 to be irreducible it means it cannot have any zeros in F. The possible polynomials are: x^2+1,x^2+x+1,x^2+\alpha x+1, x^2+(\alpha+1)x+1. Which of these polynomials has zeros in F? The ones that do not are the irreducible ones.


    can I conclude that N can only either be 1 or 3 which is \alpha and \alpha +1?

    but I realize if I would like to derive elements of field 16 using that irreducible polynomial  x^2+\alpha x+1, x^2+(\alpha+1)x+1 , it cant be done.

    unless I use  x^2+\alpha x+\alpha, x^2+(\alpha+1)x+(\alpha+1) then only I can produce 16 elements from the polynomials.

    can you guide/advise me with this?
    Last edited by classic_phohe; April 3rd 2009 at 12:01 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by classic_phohe View Post
    can I conclude that N can only either be 1 or 3 which is \alpha and \alpha +1?

    but I realize if I would like to derive elements of field 16 using that irreducible polynomial  x^2+\alpha x+1, x^2+(\alpha+1)x+1 , it cant be done.

    unless I use  x^2+\alpha x+\alpha, x^2+(\alpha+1)x+(\alpha+1) then only I can produce 16 elements from the polynomials.

    can you guide/advise me with this?
    The polynomial x^2+1, it has a zero x=1.
    The polynomial x^2+x+1, it has a zero x=\alpha.
    The polynomial x^2 + \alpha x + 1, it has no zero - so irreducible.
    The polynomial x^2+(\alpha+1)x+1, it has no zero - so irreducible.

    Therefore, F[x]/(x^2+\alpha x + 1)\text{ and }F[x]/(x^2+(\alpha+1)x+1) give rise to finite fields of 16 elements.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28
    Ok! I agree what you explained. Now let sat I choose x^2 + \alpha x + 1 to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

    x^0 = 1
    x^1 = x
    x^2 = \alpha x+ 1
    x^3 = \alpha x + \alpha
    x^4 = x + \alpha
    x^5 = 1

    From there Im stuck. Can you give some tips how should I proceed with this? or I have already done wrongly at the first place?!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by classic_phohe View Post
    Ok! I agree what you explained. Now let sat I choose x^2 + \alpha x + 1 to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

    x^0 = 1
    x^1 = x
    x^2 = \alpha x+ 1
    x^3 = \alpha x + \alpha
    x^4 = x + \alpha
    x^5 = 1

    From there Im stuck. Can you give some tips how should I proceed with this? or I have already done wrongly at the first place?!
    Any element in F[x]/(x^2+\alpha x + 1) is A+Bx + (x^2+\alpha x + 1). Let \beta = x + (x^2+\alpha x + 1). Then \text{GF}(2^4) would be A + B\beta where A,B\in \{0,1,\alpha,\alpha+1\} and \beta has the property that \beta^2 = \alpha \beta + 1 (since it solves x^2+\alpha x + 1).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28
    Quote Originally Posted by ThePerfectHacker View Post
    Any element in F[x]/(x^2+\alpha x + 1) is A+Bx + (x^2+\alpha x + 1). Let \beta = x + (x^2+\alpha x + 1). Then \text{GF}(2^4) would be A + B\beta where A,B\in \{0,1,\alpha,\alpha+1\} and \beta has the property that \beta^2 = \alpha \beta + 1 (since it solves x^2+\alpha x + 1).
    thanks for the reply, but honestly I dont quite get it. Can you please explain further?

    A+Bx + (x^2+\alpha x + 1), with \beta = x + (x^2+\alpha x + 1) how to become A + B\beta? wont this make the element become A + Bx + B(x^2+\alpha x + 1) ?
    Last edited by classic_phohe; April 5th 2009 at 05:53 AM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by classic_phohe View Post
    thanks for the reply, but honestly I dont quite get it. Can you please explain further?

    A+Bx + (x^2+\alpha x + 1), with \beta = x + (x^2+\alpha x + 1) how to become A + B\beta? wont this make the element become A + Bx + B(x^2+\alpha x + 1) ?
    The field with 16 elements is the set \{ [A+Bx]:A,B\in \mathbb{F}_4 \} where [ A + Bx] is the equivalent class modulo x^2+\alpha x+1. Notice that [A+Bx] = A[1] + B[x] where [1] is the equivalence class of 1 modulo x^2+\alpha x +1 and [x] is the equivalence class of x modulo x^2+\alpha x + 1. Thus, what I am saying is that let \beta = [x] then every element has form A + B\beta (here we thinking of A as an entire equivalence class).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28
    Quote Originally Posted by ThePerfectHacker View Post
    The field with 16 elements is the set \{ [A+Bx]:A,B\in \mathbb{F}_4 \} where [ A + Bx] is the equivalent class modulo x^2+\alpha x+1. Notice that [A+Bx] = A[1] + B[x] where [1] is the equivalence class of 1 modulo x^2+\alpha x +1 and [x] is the equivalence class of x modulo x^2+\alpha x + 1. Thus, what I am saying is that let \beta = [x] then every element has form A + B\beta (here we thinking of A as an entire equivalence class).
    thank you very much!!!

    so field with 16 elements is the set \{ [A+Bx]:A,B\in \mathbb{F}_4 \}so I will have 16 combination of A and B and hence produce 16 elements of field 16 with modulo the irreducible polynomial ; \beta^2 = \alpha \beta + 1 as \beta = [x].

    let say I proceed to field 256, I have the irreducible polynomial as x^2 + x + \nu and I just use the same method you mentioned earlier reply to determine the possible value of \nu ?

    then I shall have the elements define as \{ [A+Bx]:A,B\in \mathbb{F}_{16} \} ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Junior Member classic_phohe's Avatar
    Joined
    Feb 2009
    Posts
    28
    I believe the one you explain to me are all in polynomial basis. What if I would like to use Normal basis? Can you brief me how can it be done??

    And also, the 16 elements produced by x^2 + \alpha x + 1 are in polynomial forms, each of them represent number from 0 to 15 right? let say i would like to identify number 2 and 14, is there any direct way to find which element representations are they in?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Determine the coefficient of
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2011, 09:46 AM
  2. irreducible polynomial
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: June 4th 2010, 05:40 AM
  3. Irreducible polynomial
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 20th 2009, 02:22 AM
  4. determine irreducible quadratic polynomials
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: December 12th 2008, 09:28 AM
  5. irreducible polynomial
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: May 2nd 2008, 01:40 PM

Search Tags


/mathhelpforum @mathhelpforum