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? 


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. 
