# 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 $\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!

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

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

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

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

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

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

8. Originally Posted by classic_phohe 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 + B[x]$ where $\displaystyle $ 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).

9. Originally Posted by ThePerfectHacker 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 + B[x]$ where $\displaystyle $ 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} \}$ ?

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 $\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?

#### Search Tags

coefficient, determine, irreducible, polynomial 