-1

Help me to find all (monic as well) irreducible second degree polynomials over the field GF(4).

I know that GF(4) elements are {0,1,x,x+1} where x^2+x+1=0, and there are (4^2−4)/2=6 such irreducible polynomials, but can you name them? Like those are x^2+2, 2x^2 or I am wrong?

Gļebs Veprevs
  • 9
  • 5
    Important notational remarks: if you write the elements of $GF(4)$ as $0,1,x,x+1$ (which is fine in and of itself), then expressions like $x^2+x$ are not polynomials at all, but simply elements of $GF(4)$. Examples of polynomials over $GF(4)$ are $T+1$, $T+x$, $xT^2+(x+1)T+1$, and so on, where $T$ is a formal variable. (Also, note that $x^2+2=x^2=x+1$ and $2x^2=0$ in $GF(4)$.) This might be a little confusing, but I strongly encourage you to become comfortable with these statements before attempting the posted problem; confusions on these fundamentals will definitely prevent further progress. – Greg Martin Apr 01 '21 at 19:24
  • Actually did not get it clearly.. What are main things, when we can say that correct second degree polynomial over GF(4) is irreducible? – Gļebs Veprevs Apr 01 '21 at 19:38
  • No, there was no answer to my question – Gļebs Veprevs Apr 01 '21 at 19:43

1 Answers1

0

No, these are element of GF(4). It seems you are constructing GF(4) as $\mathbb{F}_4 = \mathbb{F}_2[x]/(x^2+x+1)$. Here $x$ is a symbolic root of the irreducible polynomial $x^2+x+1 \in \mathbb{F}_2[x]$.

Since $x$ is already a defined element, you should use a different variable for your polynomials. In other words, you are now looking for $f \in \mathbb{F}_4[T]$ such that $f$ is irreducible and degree 2. You can find all of them, since there are only $3\cdot 4 \cdot 4$ degree 2 polynomials in $\mathbb{F}_4$, although not all are unique and not all are irreducible (and not all of these are monic).

Let's look at an example. Consider $f(T) = T^2+xT+x+1$. This is a degree 2 polynomial with coefficients in GF(4). One way to check if quadratic polynomials are irreducible in a finite field is to check if any of your elements of GF(4) are roots.

Here we see that $f(x) = x^2+x^2+x+1 = x^2 = x+1$ since we are working with the fact that $x^2+x+1 = 0$ and with coefficients mod 2, so $x^2 = -x-1 = x+1$, since $-1=1$ mod 2.

$f(0) = x+1$ $f(1) = 0$, so 1 is a root. $f(x+1) = 0$, so $x+1$ is a root.

so $f(T) = (T-1)(T-(x+1))$, hence it is reducible.

You can do similar techniques for all of the monic quadratic polynomials in $\mathbb{F}_4[T]$ to see which are irreducible. You only need to look at monic polynomials since you can always factor the leading coefficient out.

Indy500
  • 33