How to factor a polynomial over finite fields?

Question

We want to study the factorization of a specific polynomial with coefficients over finite fields. Let $f\in \mathbb{Z}$ a polynomial, we define the polynomial class as follows: suppose $(\bar{f})$ $\in \mathbb{Z}_p$ such that its factorization is $\bar{f}(x)=\bar{f}_1(x)^{e_1}...\bar{f}_g(x)^{e_g}\in \mathbb{F}_p[x]$. Then we denote its class as $d_1^{e_1},...,d_g^{e_g}$. As an example, a polynomial of degree 2 may has class $(2)$, $(1^2)$ or $(1,1)$.

Is there any classification for polynomials up to $5^{th}$ degree related to Legendre Symbol and discriminant?

Answer 1

Maybe this theorem can be useful:

Theorem: Let $f(x)$ be a monic polynomial od degree $n$ with integral coefficients in a $p$-adic field F. Assume that $\bar{f}(x)$ has no repeated roots. Let $r$ be the number of irreductible factors of $\bar{f(x)}$ over the residue class field. Then $r \equiv n$ mod $2$ if and only if the discriminant is a square in F.

Answer 2

The theorem @dark43 mentions goes back to Stickelberger. A proof can be found in R. G. Swan, Factorization of polynomials over finite fields. Pacific J. Math., 12:1099–1106, 1962.

For $p$ prime and $f\in\mathbb{Z}[X]$ monic of degree $n$ and discriminant $\Delta_{f}$, with $\bar{f}=\bar{f_1}^{e_1}...\bar{f_g}^{e_g}$ in $\mathbb{F}_p[x]$, the $\bar{f_i}$ being irreducible and different, it yields the following:

• $f$ has repeated factors in $\mathbb{F}_{p}[X]$, that is, at least one of the exponents $e_{i}\geq2$, iff $p$ divides $\Delta_{f}$; assume that $\Delta_{f} \not\equiv0\text{ mod }p$ from now on
• if $f$ is irreducible in $\mathbb{F}_{p}[X]$, $(\frac{\Delta_{f}}{p})=(-1)^{n-1}$, where $(\frac{\Delta_{f}}{p})$ denotes the Kronecker symbol; it agrees with the Legendre symbol for odd $p$, and $(\frac{a}{2})=1$ iff $a\equiv\pm1\text{ mod }8$; basic argument: $\Delta_{f}$ is a square iff the Galois group $G\subseteq S_{n}$ consists of even permutations; but $G$ is cyclic and transitive, so it is generated by an $n$-cycle $(1\cdots n)$, and $(1\cdots n)\in A_{n}$ iff $n$ is odd
• for example, the cyclotomic polynomial $\Phi_{8}=X^{4}+1$ has discriminant $256=16^{2}$ and $n=4$, hence it cannot be irreducible in $\mathbb{F}_{p}[X]$ for odd $p$ (and $\Phi_{8}=(X+1)^{4}$ has repeated factors in $\mathbb{F}_{2}[X]$)
• generally, $(\frac{\Delta_{f}}{p})=(-1)^{n-g}=(-1)^{s}$, where $s$ is the number of the irreducible factors $\bar{f_{i}}$ that are of even degree $d_i$; so the discriminant determines $g$ (the number of irreducible factors of $\bar{f}$) modulo 2, as well as $s$ (the number of $i$ with $d_i$ even) modulo 2.

When $p\not\mid\Delta_{f}$ and $\mathbb{Z}_p$ is the ring of integers of the $p$-adic field $\mathbb{Q}_p$, $f$ factorizes as $f_1...f_g$ in $\mathbb{Z}_p[x]$ for suitable polynomials $f_i$ for which $f_i\text{ mod }p = \bar{f_i}$, by Hensel's Lemma, and one has $(\frac{\Delta_{f}}{p})=1$ iff $\Delta_{f}$ is a square in $\mathbb{Z}_p$. These are further ingredients for the proof.