# Splitting fields of Polynomials over finite fields of non-prime order

Suppose we wish to find the splitting field $F$ of a polynomial $f(x)$, of degree $m$, over a finite field $K$ with $|K| = p^n$ for some $n$. If one can show that this polynomial is irreducible then we know that $|F:K| = deg(f) = m$. Hence by tower law $|F:{\rm I\!F}_{p}| = |F:K|\cdot |K:{\rm I\!F}_{p}| = m \cdot n$. So due uniqueness of finite fields of a given order we know that $F \cong {\rm I\!F}_{p^{mn}}$

When $n=1$ and $m \leq 3$, this is fairly trivial since then $K$ can be realised as the integers mod $p$, and $f$ is irreducible if and only if it has no roots. When $n=1$ and $m \geq 4$, the problem is still approachable, since we can still realise the field $K$ as the integers modulo $p$, and then we can just check all possible factors of $f$.

However, when $n \neq 1$, the field $K$ is realised as the quotient ${\rm I\!F}_{p}[x] /<g(x)>$, where $g$ is an irreducible polynomial of degree $n$ in ${\rm I\!F}_{p}[x]$. Then it becomes much harder to show that a polynomial in $K[x]$ is irreducible. If $m = 2$ we can attempt to show that it has no roots, perhaps by completing the square and using arguments about to multiplicative group $K^{\times}$ of units of $K$. When $m \geq 3$ I'm not sure how to proceed.

A motivating example:

Consider $K$ a field of 27 elements and $f(x) = x^4 + 1 \in K[x]$. I can show it has no roots, since $|K^{\times}| = |K| - 1 = 26$ by Lagrange's theorem, the multiplicative order of any non-zero element in $K$ divides $26$. If $a \in K$ is a root of $f$ (so in particular $a \neq 0,1$), then $a^4 = -1$ and, since $K$ has characteristic $3$ and so $-1 \neq 1$, the multiplicative order of $a$ does not divide $4$, and so the multiplicative order is $13$ or $26$. In particular $a^8 \neq 1$ contradicting that $a$ is a root of $f(x) = x^4 + 1$.

Hence if $f$ is not irreducible in $K[x]$ then it must factor as a product of two quadratic polynomials since it has no roots in $K$. Then it is easy to see that such a factorisation must be of the form:

$$f(x) = (x^{2} + ax + b)(x^{2} - ax + b^{-1}) \hspace{0.6cm} \text{where} \hspace{0.6cm} b^{-1} + b - a^{2} = 0,\hspace{0.2cm} \text{and},\hspace{0.2cm} ab^{-1} - ab = 0$$

Then the problem comes down to finding if there are such an $a$ and $b$ in $K$ satisfying those relations. I feel like this is a non-trivial problem and I don't know how to approach it. This is furthest I could go:

$$ab^{-1} - ab = 0 \Rightarrow a(1 - b^{2}) = 0 \Rightarrow a=0\text{ or } b^{2} = 1$$

Then we check cases:

$$a=0 \Rightarrow b^{-1} + b=0 \Rightarrow b^{2} = -1,$$

Then I get stuck. If we were working over a field of prime order, I could use the Lagrange symbol to check if $-1$ is a quadratic residue. But I don't know how to take square roots in fields of non prime order. Similarly, if $a\neq 0$ and so $b^{2} = 1$ I don't know how to proceed.

Is there a better method than the one I am using?

• $b^2=-1$ is soluble in a field of finite odd order $q$ iff $q\equiv1\pmod 4$. – Lord Shark the Unknown May 12 '18 at 9:48

There's always Berlekamp's algorithm.

$x^4+1$ has quadratic factors over all finite fields. If $q$ is an odd prime power, $q^2\equiv1\pmod8$ and so $GF(q^2)$ has primitive eighth roots of unity. So $x^4+1$ splits into linear factors in $GF(q^2)$ and so into quadratic factors in $GF(q)$.

One way to detect whether a polynomial over $GF(q)$ has an irreducible factor of degree $d$ is to take its gcd with $x^{q^d}-x$.

• I can see that, for $q$ an odd prime power, $GF(q^{2})$ always has primitive eight roots of unity, and so $x^4 + 1$ splits in to linear factors in $GF(q^{2})$, but I don't see how we can conclude then that it splits in to quadratic factors in $GF(q)$. Is this some sort of tower law degree argument? – Adam Higgins May 12 '18 at 10:16

Following the help from Lord Shark the Unknown, I'm going to answer my own question fully, in case anyone ever has similar questions.

Following the notation set up in my original question, we know that $a=0$ or $b^{2}=1$. If $a=0$ then $b^{2} = -1$, but then $b^{4} = 1$, and since the multiplicative order of any element of $K - \{0,1\}$ is 2, 13, or 26, we see that $b^{4} \neq 1$, and so $b^{2} \neq -1$. Hence $a \neq 0$ and so $b^{2} = 1$. This gives us the factorisation.

$$f(x) = x^{4} + 1 = (x^{2} + x + 2)(x^{2} - x + 2)$$

Then, if $g(x) = x^{2} + x + 2$, and $h(x) = x^{2} - x + 2$. We see that, by completing the square and remembering that $K$ has characteristic 3, $g(x) = (x + 2)^{2} + 1$ and $h(x) = (x + 1)^{2} + 1$. Hence $f$ has all its roots in a field extension of $K$ that contains a square root of $-1$. Let $\alpha$ be a root of $x^{2} + 1$ in some field extension. Then $K(\alpha)$ has all the roots of f, and $|K(\alpha):K|$ = 2, so $K(\alpha)$ is the field with $3^{6}$ elements.