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? 

 A: 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. :)
A: 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.
A: 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. 
