# Factoring over a finite field

Consider $f=x^4-2\in \mathbb{F}_3[x]$, the field with three elements. I want to find the Galois group of this polynomial.

Is there an easy or slick way to factor such a polynomial over a finite field?

-
It's a quartic, so first look for roots and then check the quadratics. There aren't that many possibilities for roots or irreducible quadratics, so you can do this pretty quickly without too much trouble. – Brett Frankel Apr 28 '12 at 19:42
@BrettFrankel, like this? $x^{4}-2=(x^{2}+\sqrt{2})(x^{2}-\sqrt{2})$. I can do this over $\mathbb{Q}$, but I am not sure what $\sqrt{2}$ corresponds to in $\mathbb{F}_{3}$. – Edison Apr 28 '12 at 19:45
Well, there's a sign error. Also, 2 has no squareroot in $\mathbb{F}_3$. What I meant was, make a list of the irreducible quadratics over $\mathbb{F}_3$ and check whether any of them divide $f$. – Brett Frankel Apr 28 '12 at 19:47

Recall that over $\mathbb{F}_q$, the polynomial $x^{q^n} - x$ is precisely the product of all irreducible polynomials of degree dividing $n$. The following then gives a straightforward algorithm to determine the degrees of the irreducible factors of a polynomial $f(x)$ over $\mathbb{F}_q$:

• Initialize $g(x) := \frac{f(x)}{\gcd(f(x), f'(x))}$ (this removes repeated factors) and $n := 1$.
• Compute $\gcd(g(x), x^{q^n} - x)$ via the Euclidean algorithm. This is the product of all irreducible factors of $f$ of degree $n$.
• Set $g(x) := \frac{g(x)}{\gcd(g(x), x^{q^n} - x)}$ and $n := n+1$.
• Repeat.

In this case by inspection $f$ has no linear factors so we only have to check for quadratic factors, hence we only have to compute $\gcd(x^4 - 2, x^9 - x)$. But again by inspection, $$(x^4 - 2)(x^4 + 2) = x^8 - 1$$

so in fact $x^4 - 2$ must be a product of two (distinct) irreducible quadratics.

-
Ok, I get it. Thanks for the great answer. – Edison Apr 28 '12 at 22:34

The coefficients are reduced modulo 3, so $$x^4-2=x^4-3x^2+1=(x^4-2x^2+1)-x^2=(x^2-1)^2-x^2=(x^2+x-1)(x^2-x-1).$$

It is easy to see that neither $x^2+x-1$ nor $x^2-x-1$ have any roots any $F_3$. As they are both quadratic, the roots are in $F_9$. Therefore the Galois group is $Gal(F_9/F_3)$, i.e. cyclic of order two.

-

In this case, there is a straightforward, mindless thing to do:

• Is $\sqrt{2} \in \mathbb{F}_3$?
• If yes, then does $\sqrt{2}$ have a square root in $\mathbb{F}_3$?
• If yes, then the splitting field of $f$ is $\mathbb{F}_3$
• If no, then the splitting field of $f$ is $\mathbb{F}_9 (\cong \mathbb{F}(\sqrt[4]{2}))$
• If no, then $\mathbb{F}_9 \cong \mathbb{F}_3(\sqrt{2})$. Does $\sqrt{2}$ have a square root in $\mathbb{F}_9$?
• If yes, then the splitting field of $f$ is $\mathbb{F}_9$
• If no, then the splitting field of $f$ is $\mathbb{F}_{81} (\cong \mathbb{F}_3(\sqrt[4]{2})$

And in all cases, you can refine the argument to find all of the roots, and/or to find the factors of $f$.

We can get a bit of a shortcut by observing all of the fourth roots of unity have to be in the splitting field of $f$, so $\mathbb{F}_9$ has to be involved.

We can get even more of a shortcut by observing, for $x \in \overline{\mathbb{F}_3} \setminus 0$:

• $x \in \mathbb{F}_3$ if and only if $x^2 = 1$
• Therefore $x^4 \in \mathbb{F}_3$ if and only if $x^8 = 1$
• $x \in \mathbb{F}_9$ if and only if $x^8 = 1$
• Therefore $x^4 \in \mathbb{F}_3$ if and only if $x \in \mathbb{F}_9$

If we just want the Galois group, we can stop here. :)

-