Thread: How to determine coefficient in irreducible polynomial? HELP!!

1. 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!

2. Originally Posted by classic_phohe
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.

3. Originally Posted by ThePerfectHacker
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?

4. Originally Posted by classic_phohe
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.

5. 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?!

6. Originally Posted by classic_phohe
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$).

7. Originally Posted by ThePerfectHacker
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)$ ?

8. Originally Posted by classic_phohe
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).

9. Originally Posted by ThePerfectHacker
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} \}$ ?

10. 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?