Factoring Polynomials in Fields

Question

I always have problems to factorize polynomials that have no linear factors any more. For example ($x^5-1$) in $\mathbb{F}_{19}$. It's easy to find the root 1 and to split it. ($x^5-1$) = ($x-1$) * ($x^4$+$x^3$+$x^2$+x+1). I think the last part must split into two irreducible polynomials with degree 2. ($x^2$+ ax+ b) ($x^2$+ Cx+ d). I expanded it and compared the coefficients to find values for a,b,c,d. But it wasn't solvable.

Is this approach correct or a there any other procedures or tricks to solve such a problem ? Thank you.

Answer 1

Your suspicion is correct: $(x^5 - 1)$ does split into a linear factor and two quadratic ones. Your approach even works out!

$(x^2 + ax + b)(x^2 + bx + c) = x^4 + (a+c)x^3 + (b + ac + d)x^2 + (ad+bc)x + bd$

So we have

$bd = 1$, $a + c = 1$, $ad+bc = 1$, $b + ac + d = 1$.

Immediately we derive

$d = \frac{1}{b}$, $c = 1-a$.

We then substitute in $ad+bc = 1$ to obtain

$a = \frac{1-b}{\frac{1}{b}-b}$

This alerts us that we have to be careful to check $b \in \{1,18\}$ separately.

If $b$ happens to be $1$, then we get that $1 = b + ac + d = 1 + ac + 1 = 2+ac$, and so $1 + ac = 0$. As it happens, this equation and $c = 1-a$ are satisfied when $a$ is $5$, yielding $c$ as $-4$. This gives our two irreducibles.

Answer 2

There is a trick to see that the polynomial is reducible. The multiplicative group $\mathbb{F}_{19^2}^*$ of the field of $19^2$ elements has $19^2 - 1 \equiv 0 \mod 5$ elements, so it contains a fifth root of unity. So the minimal polynomial of a fifth root of unity over $\mathbb{F}_{19}$, which divides $x^5 - 1$, has degree $2$. So your polynomial splits into quadratics.

I don't know a good way to find the factorization though, besides brute force. It turns out to be $x^5 - 1 = (x - 1)(x^2 + 5x + 1)(x^2 - 4x + 1)$.