Results 1 to 10 of 10

Thread: 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 $\displaystyle GF(2^2)$ that is $\displaystyle x^2 + Nx + 1$, (N = elements of $\displaystyle GF(2)$) how do I determine the possible values of N ? Given the irreducible polynomial for $\displaystyle GF(2)$ is $\displaystyle 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 $\displaystyle GF(2^2)$ that is $\displaystyle x^2 + Nx + 1$, (N = elements of $\displaystyle GF(2)$) how do I determine the possible values of N ? Given the irreducible polynomial for $\displaystyle GF(2)$ is $\displaystyle x^2 + x + 1$

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

    For $\displaystyle x^2 + Nx+1$ to be irreducible it means it cannot have any zeros in $\displaystyle F$. The possible polynomials are: $\displaystyle 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 $\displaystyle 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, $\displaystyle F=\mathbb{Z}_2[t]/(t^2+t+1)$. Therefore, $\displaystyle F = \{ 0,1,\alpha,\alpha+1\}$ where $\displaystyle \alpha = t + (t^2+t+1)$ and $\displaystyle \alpha^2 = \alpha + 1$.

    For $\displaystyle x^2 + Nx+1$ to be irreducible it means it cannot have any zeros in $\displaystyle F$. The possible polynomials are: $\displaystyle 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 $\displaystyle F$? The ones that do not are the irreducible ones.


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

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

    unless I use $\displaystyle 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; Apr 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 $\displaystyle \alpha$ and $\displaystyle \alpha +1$?

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

    unless I use $\displaystyle 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 $\displaystyle x^2+1$, it has a zero $\displaystyle x=1$.
    The polynomial $\displaystyle x^2+x+1$, it has a zero $\displaystyle x=\alpha$.
    The polynomial $\displaystyle x^2 + \alpha x + 1$, it has no zero - so irreducible.
    The polynomial $\displaystyle x^2+(\alpha+1)x+1$, it has no zero - so irreducible.

    Therefore, $\displaystyle 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 $\displaystyle x^2 + \alpha x + 1 $ to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

    $\displaystyle x^0 = 1$
    $\displaystyle x^1 = x$
    $\displaystyle x^2 = \alpha x+ 1$
    $\displaystyle x^3 = \alpha x + \alpha$
    $\displaystyle x^4 = x + \alpha$
    $\displaystyle 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 $\displaystyle x^2 + \alpha x + 1 $ to be the irreducible polynomial, hence I use this to produce the elements in field of 16:

    $\displaystyle x^0 = 1$
    $\displaystyle x^1 = x$
    $\displaystyle x^2 = \alpha x+ 1$
    $\displaystyle x^3 = \alpha x + \alpha$
    $\displaystyle x^4 = x + \alpha$
    $\displaystyle 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 $\displaystyle F[x]/(x^2+\alpha x + 1)$ is $\displaystyle A+Bx + (x^2+\alpha x + 1)$. Let $\displaystyle \beta = x + (x^2+\alpha x + 1)$. Then $\displaystyle \text{GF}(2^4)$ would be $\displaystyle A + B\beta$ where $\displaystyle A,B\in \{0,1,\alpha,\alpha+1\}$ and $\displaystyle \beta$ has the property that $\displaystyle \beta^2 = \alpha \beta + 1$ (since it solves $\displaystyle 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 $\displaystyle F[x]/(x^2+\alpha x + 1)$ is $\displaystyle A+Bx + (x^2+\alpha x + 1)$. Let $\displaystyle \beta = x + (x^2+\alpha x + 1)$. Then $\displaystyle \text{GF}(2^4)$ would be $\displaystyle A + B\beta$ where $\displaystyle A,B\in \{0,1,\alpha,\alpha+1\}$ and $\displaystyle \beta$ has the property that $\displaystyle \beta^2 = \alpha \beta + 1$ (since it solves $\displaystyle x^2+\alpha x + 1$).
    thanks for the reply, but honestly I dont quite get it. Can you please explain further?

    $\displaystyle A+Bx + (x^2+\alpha x + 1)$, with $\displaystyle \beta = x + (x^2+\alpha x + 1)$ how to become $\displaystyle A + B\beta$? wont this make the element become $\displaystyle A + Bx + B(x^2+\alpha x + 1)$ ?
    Last edited by classic_phohe; Apr 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?

    $\displaystyle A+Bx + (x^2+\alpha x + 1)$, with $\displaystyle \beta = x + (x^2+\alpha x + 1)$ how to become $\displaystyle A + B\beta$? wont this make the element become $\displaystyle A + Bx + B(x^2+\alpha x + 1)$ ?
    The field with 16 elements is the set $\displaystyle \{ [A+Bx]:A,B\in \mathbb{F}_4 \}$ where $\displaystyle [ A + Bx]$ is the equivalent class modulo $\displaystyle x^2+\alpha x+1$. Notice that $\displaystyle [A+Bx] = A[1] + B[x]$ where $\displaystyle [1]$ is the equivalence class of $\displaystyle 1$ modulo $\displaystyle x^2+\alpha x +1$ and $\displaystyle [x]$ is the equivalence class of $\displaystyle x$ modulo $\displaystyle x^2+\alpha x + 1$. Thus, what I am saying is that let $\displaystyle \beta = [x]$ then every element has form $\displaystyle A + B\beta$ (here we thinking of $\displaystyle 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 $\displaystyle \{ [A+Bx]:A,B\in \mathbb{F}_4 \}$ where $\displaystyle [ A + Bx]$ is the equivalent class modulo $\displaystyle x^2+\alpha x+1$. Notice that $\displaystyle [A+Bx] = A[1] + B[x]$ where $\displaystyle [1]$ is the equivalence class of $\displaystyle 1$ modulo $\displaystyle x^2+\alpha x +1$ and $\displaystyle [x]$ is the equivalence class of $\displaystyle x$ modulo $\displaystyle x^2+\alpha x + 1$. Thus, what I am saying is that let $\displaystyle \beta = [x]$ then every element has form $\displaystyle A + B\beta$ (here we thinking of $\displaystyle A$ as an entire equivalence class).
    thank you very much!!!

    so field with 16 elements is the set $\displaystyle \{ [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 ;$\displaystyle \beta^2 = \alpha \beta + 1$ as $\displaystyle \beta = [x]$.

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

    then I shall have the elements define as $\displaystyle \{ [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 $\displaystyle 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: Nov 17th 2011, 09:46 AM
  2. irreducible polynomial
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Jun 4th 2010, 05:40 AM
  3. Irreducible polynomial
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Feb 20th 2009, 02:22 AM
  4. determine irreducible quadratic polynomials
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: Dec 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