Determining Possible Values of N for Irreducible Polynomial in GF(2^2)

[classic_phone]

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

I think since the field is GF(4) so we have choice of \{ 0,1, \alpha, \alpha + 1\}

thus to make the polynomial irreducible N could be either 1 or 3 which is \alpha or \alpha + 1.

so now i have polynomial of either x^2 + \alpha x + 1 or x^2 + (\alpha +1 )x + 1

then how do I use the polynomial to generate the 16 elements for the field of GF((2^2)^2) ?? please guide me with some steps.

thanks alot

 

[adriank]

Remember that a polynomial of degree 2 or 3 is irreducible if and only if it has no root.

And in general, if you have a field F and an irreducible polynomial p(x) of degree n, then F[x]/<p(x)> is a field with |F|ⁿ elements.

 

[classic_phone]

Remember that a polynomial of degree 2 or 3 is irreducible if and only if it has no root.

And in general, if you have a field F and an irreducible polynomial p(x) of degree n, then F[x]/<p(x)> is a field with |F|ⁿ elements.

Hmmm, I am quite confirmed that for the norm to be 1, N has to be either \alpha or \alpha + 1 or in integer is either 1 or 3.

Now I am very troubled, which is 1? \alpha or \alpha +1 ? and how do I identify it??

 

[adriank]

Neither is; the extra elements \alpha and \alpha + 1 don't really correspond with the other numbers (there is no 3 anywhere!); they are separate elements on their own. It might help to describe the multiplication table of GF(2²), with \alpha being the element that is a root of x² + x + 1. All you need to do that is to remember that since \alpha^2 + \alpha + 1 = 0, you have \alpha^2 = -(\alpha + 1) = \alpha + 1. Then the multiplication table is
<br /> \begin{tabular}{c|cccc}<br /> &amp; 0 &amp; 1 &amp; $\alpha$ &amp; $\alpha + 1$ \\ \hline<br /> 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\<br /> 1 &amp; 0 &amp; 1 &amp; $\alpha$ &amp; $\alpha + 1$ \\<br /> $\alpha$ &amp; 0 &amp; $\alpha$ &amp; $\alpha + 1$ &amp; 1 \\<br /> $\alpha + 1$ &amp; 0 &amp; $\alpha + 1$ &amp; 1 &amp; $\alpha$<br /> \end{tabular}<br />

It seems like what you want to do is construct GF(2⁴) by finding a monic irreducible polynomial of degree 2 over GF(2²). So let's do that:

Say we're trying to find a monic irreducible polynomial of the form p(x) = x² + Nx + 1, and we need to find N. That means we need to pick N such that this polynomial has no root. This is not the same polynomial as x² + x + 1, which was used to construct GF(2²)! I think that might be where the confusion is coming from.

Anyway, there are really only four possibilities for N, so check each of them. If N = 0, then p(1) = 0; if N = 1, then p(\alpha) = 0 by the definition of \alpha. It seems like both N = \alpha and N = \alpha + 1 work. Pick either one; then GF(2²)[x]/<p(x)> will be the required field with 16 elements.

 

[classic_phone]

Hi, Thanks for your reply!

I get what you mean. I am confused with the 1 and 3 in relation to \alpha and \alpha + 1 because I have asked similar question to other person before and this is how he explain:

x^2+x+ N has degree 2. so it's irreducible iff it has no root in \text{GF}(4). thus the polynomial is irreducible for all odd values of N in \text{GF}(4) because x^2+x is always even. so the only possible values of N. is 1 and 3. as the element in \text{GF}(4) = {0,1,2,3}


Hence I try the same way to check on x^2+ Nx + 1 when I try all the 4 possible numbers in the equation; I get only N=1 or 3 that will make the polynomial irreducible .

and I agreed that when N is either \alpha and \alpha + 1, the polynomial is irreducible.

Therefore, I have no idea how to relate the number 1 and 3 to \alpha and \alpha + 1

 

[classic_phone]

Neither is; the extra elements \alpha and \alpha + 1 don't really correspond with the other numbers (there is no 3 anywhere!); they are separate elements on their own. It might help to describe the multiplication table of GF(2²), with \alpha being the element that is a root of x² + x + 1. All you need to do that is to remember that since \alpha^2 + \alpha + 1 = 0, you have \alpha^2 = -(\alpha + 1) = \alpha + 1. Then the multiplication table is
<br /> \begin{tabular}{c|cccc}<br /> &amp; 0 &amp; 1 &amp; $\alpha$ &amp; $\alpha + 1$ \\ \hline<br /> 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\<br /> 1 &amp; 0 &amp; 1 &amp; $\alpha$ &amp; $\alpha + 1$ \\<br /> $\alpha$ &amp; 0 &amp; $\alpha$ &amp; $\alpha + 1$ &amp; 1 \\<br /> $\alpha + 1$ &amp; 0 &amp; $\alpha + 1$ &amp; 1 &amp; $\alpha$<br /> \end{tabular}<br />

It seems like what you want to do is construct GF(2⁴) by finding a monic irreducible polynomial of degree 2 over GF(2²). So let's do that:

Say we're trying to find a monic irreducible polynomial of the form p(x) = x² + Nx + 1, and we need to find N. That means we need to pick N such that this polynomial has no root. This is not the same polynomial as x² + x + 1, which was used to construct GF(2²)! I think that might be where the confusion is coming from.

Anyway, there are really only four possibilities for N, so check each of them. If N = 0, then p(1) = 0; if N = 1, then p(\alpha) = 0 by the definition of \alpha. It seems like both N = \alpha and N = \alpha + 1 work. Pick either one; then GF(2²)[x]/<p(x)> will be the required field with 16 elements.

Is there any easier and faster way to check what are the possible coefficient that make the polynomial irreducible. The example we discussed earlier only hav 4 possible elements to choose on. Let say if now I am looking at x^2 + \nu x + 1 and that \nu is of the field of GF(2<sup>2) (the 16 elements generated from x^2 + N x + 1 ) . It will be very hard if I need to check each of the elements one by one.

any advice on that?</sup>

 

[adriank]

The elements of GF(4) are not 0, 1, 2, and 3, so don't think of them as such. GF(4) is still a field of characteristic 2 (i.e. 2 = 0). Likewise, don't think of x² + x being even, since that only makes sense in the integers, and \alpha is not an integer. As GF(2) is a subfield of GF(4), you can't write \alpha in terms of the elements of GF(2) (which are 0 and 1); really what's going on is that GF(4) is a vector space over GF(2), and \{1, \alpha\} is a basis of that vector space.

When you're picking values of N, you have to pick elements of GF(4), and 2 and 3 are not considered elements of GF(4). (That is, unless you declare that 2 = 1 + 1 = 0, and 3 = 2 + 1 = 1.)Unfortunately, I don't know of any quicker way to find coefficients that make a polynomial irreducible.

 

[classic_phone]

The elements of GF(4) are not 0, 1, 2, and 3, so don't think of them as such. GF(4) is still a field of characteristic 2 (i.e. 2 = 0). Likewise, don't think of x² + x being even, since that only makes sense in the integers, and \alpha is not an integer. As GF(2) is a subfield of GF(4), you can't write \alpha in terms of the elements of GF(2) (which are 0 and 1); really what's going on is that GF(4) is a vector space over GF(2), and \{1, \alpha\} is a basis of that vector space.

When you're picking values of N, you have to pick elements of GF(4), and 2 and 3 are not considered elements of GF(4). (That is, unless you declare that 2 = 1 + 1 = 0, and 3 = 2 + 1 = 1.)


Unfortunately, I don't know of any quicker way to find coefficients that make a polynomial irreducible.

ok ok! really thanks a lot for the info! all this while I have confused myself with the elements and integers.

So I got to try all the 16 elements for \nu and for each \nu value I need to try out all 16 possible elements in the polynomial to check if it will result in 0. The \nu that does not result in 0 is the potential coefficient that I can use?

Am I on the right track?

 

[adriank]

Well, if you're trying to construct GF(16) from GF(4), you need an irreducible polynomial p(x) of degree 2 in GF(4)[x]; that is, p(x) has coefficients in GF(4) and has no root in GF(4). Thus you only need to check 4 values. Once you construct GF(16), p(x) will necessarily have a root in GF(16).

 

[classic_phone]

Well, if you're trying to construct GF(16) from GF(4), you need an irreducible polynomial p(x) of degree 2 in GF(4)[x]; that is, p(x) has coefficients in GF(4) and has no root in GF(4). Thus you only need to check 4 values. Once you construct GF(16), p(x) will necessarily have a root in GF(16).

yah, but if I were to try to construct GF(256) from GF(16), I need an irreducible polynomial p(x) of degree 2 in GF(16)[x] . since the polynomial has coefficients in GF(16) and no root in GF(16), I need to check 16 values right??

 

[adriank]

I guess so.

I might be wrong; there might be easier ways of finding irreducible polynomials.

 

[classic_phone]

anyway, thanks a lot adriank ! you have do me a great help!

thank you very much! :D

 

[Hurkyl]

A randomly chosen monic quadratic polynomial over GF(q) (with q a power of 2) has a 50% chance of being irreducible: there are q^2 such polynomials, and and q^2 / 2 different ways to choose a product of two monic linear polynomials.

So if your goal is to simply find an irreducible polynomial, all you have to do is keep picking them at random until you find one that works.

There is a faster way to tell if your quadratic factors, using the polynomial identity (valid in any finite field, not just in ones with characteristic 2)"
x^q - x = \prod_{a \in GF(q)} (x - a)

From this, we see that f(x) is an irreducible quadratic if and only if
GCD(f(x), x^q - x) = 1

The computational hook that makes this fast is to use square-and-multiply-type algorithsm to compute a modular exponentiation (which is especially fast in characteristic 2!)
g(x) \equiv x^q \pmod{f(x)}

and thus
GCD(f(x), x^q - x) = GCD(f(x), g(x) - x)

 

[classic_phone]

A randomly chosen monic quadratic polynomial over GF(q) (with q a power of 2) has a 50% chance of being irreducible: there are q^2 such polynomials, and and q^2 / 2 different ways to choose a product of two monic linear polynomials.

So if your goal is to simply find an irreducible polynomial, all you have to do is keep picking them at random until you find one that works.

There is a faster way to tell if your quadratic factors, using the polynomial identity (valid in any finite field, not just in ones with characteristic 2)"
x^q - x = \prod_{a \in GF(q)} (x - a)

From this, we see that f(x) is an irreducible quadratic if and only if
GCD(f(x), x^q - x) = 1

The computational hook that makes this fast is to use square-and-multiply-type algorithsm to compute a modular exponentiation (which is especially fast in characteristic 2!)
g(x) \equiv x^q \pmod{f(x)}

and thus
GCD(f(x), x^q - x) = GCD(f(x), g(x) - x)

actually i need to determine all the possible value \nu that is make the polynomial irreducible. you explanation seems so complicated. do you mind simplify it for me?

 

[Hurkyl]

actually i need to determine all the possible value \nu that is make the polynomial irreducible.

Oh, so it's going to be a tedious problem no matter how you do it. Anyways, a direct translation of what you seek (or rather, its opposite) is:

It's not irreducible, then
x^2 + \nu x + 1 = (x + \rho) (x + 1 / \rho)
for some \alpha, and therefore \nu = \rho + 1 / \rho.​

This gives a straightforward way to write down all of the \nu which make the polynomial reducible.

 

[classic_phone]

hmm why is it \nu = \rho + 1/\rho ? what are the values of \rho ?

 

[adriank]

If (x + a)(x + b) = x² + cx + 1, then ab = 1, so b = a^-1.

 

[classic_phone]

If (x + a)(x + b) = x² + cx + 1, then ab = 1, so b = a^-1.

so now, what I need to do is find all \nu = (\rho + 1/\rho) with \rho all the elements in GF(16). And all the \nu that I have, are the one make the polynomial reducible.

Now my doubt is how do i do for 1/\rho ? let say we try element \lambda x + \lambda with \lambda elements from GF(4)