Roots of polynomials over finite fields

A root $a$ of $f$ in a field $K$ is the same as a linear factor $x - a$, so finding all roots of $f \in \mathbb{F}_q[x]$ is the part of the factorisation that concerns factors of degree 1 (Factoring polynomials over finite fields). It is much cheaper than a complete factorisation, because only one distinct-degree step is needed and the splitting does not require the trace map. Over the ring $\mathbb{Z}/n\mathbb{Z}$ with $n$ composite the situation is different: a polynomial can have more roots than its degree, and the roots are found prime by prime.

Roots in a finite field#

By Theorem 1 of Factoring polynomials over finite fields with $d = 1$,

so for squarefree $g$ the product of the linear factors of $g$ is $\gcd(g, x^q - x)$. For odd $q$ the nonzero elements split further:

The same splitting applies to the shifted roots $a + c$, which gives a randomised equal-degree factorisation for $d = 1$, due to Berlekamp [Ber1970] and Rabin [Rab1980b]:

Step 3 discards all factors of $g$ of degree at least 2 and already splits the roots into two classes; this initial split is Rabin's. In step 4 a root $\rho$ of $u$ goes into the gcd if and only if $\rho + c$ is a nonzero square, which for a uniformly random $c$ happens with probability about $1/2$, independently enough for distinct roots that a piece of degree $m$ is split with probability at least $4/9$ (Lemma 7 of Factoring polynomials over finite fields) and the expected depth of the recursion is $O(\log n)$. Each level costs exponentiations of total degree $O(n)$, so the expected total cost is $O(M(n) \log q \log n)$, dominated by the exponentiations.

Powers of $x + c$. An exponentiation $x^e \bmod u$ is cheaper than $a^e \bmod u$ for a general $a$, since the multiplications by $x$ in the square-and-multiply loop are shifts. FLINT uses this for the random shifts when $q$ has more than 16 bits:

So $(x + c)^{(q-1)/2} \bmod u$ costs two Taylor shifts of degree $m$ (Taylor shifts) and one exponentiation of $x$.

Distinct nonzero roots. When $f$ is known to split into distinct linear factors $x - a$ with $a \ne 0$, as in the decoding of Reed–Solomon codes and in sparse interpolation, the squarefree factorisation is unnecessary, and step 3 decides at once whether $f$ has this form: the degrees of $u_1$ and $u_2$ add up to $\deg f$ if and only if it does. nmod_poly_find_distinct_nonzero_roots and fmpz_mod_poly_find_distinct_nonzero_roots implement this test and the splitting (see Finding roots that are expected to be distinct).

Roots modulo prime powers#

Let $f \in \mathbb{Z}[x]$ and $k \ge 2$. Every root of $f$ modulo $p^k$ reduces to a root modulo $p^e$ for every $e \le k$, so the roots modulo $p^k$ can be found by lifting all roots modulo $p$, doubling the precision in each step. Unlike the classical form of Hensel's lemma [Hen1908] (see also Hensel lifting for the lifting of factorisations), this lifts roots that are multiple modulo $p$ as well.

The linear congruence $\alpha t \equiv \beta \pmod{p^s}$ has no solution if $p^j = \gcd(\alpha, p^s)$ does not divide $\beta$, and otherwise exactly $p^j$ solutions modulo $p^s$, an arithmetic progression with step $p^{s-j}$ (computed by fmpz_divides_mod_list). Hence a simple root modulo $p$ ($f'(a) \not\equiv 0$) lifts to exactly one root modulo $p^k$, while a multiple root can lift to none or to many. The lifts $a + p^e t$ for $t$ modulo $p^{e'-e}$ are distinct modulo $p^{e'}$, and every root modulo $p^{e'}$ arises from its reduction modulo $p^e$, so lifting every root at every step enumerates all roots modulo $p^k$. If $f \equiv 0 \pmod p$, all $p$ residues are roots modulo $p$ and are lifted in the same way.

The number of roots can be large: the roots of $x^2$ modulo $p^k$ are the multiples of $p^{\lceil k/2 \rceil}$, of which there are $p^{\lfloor k/2 \rfloor}$.

Composite moduli#

For $n = \prod_j p_j^{k_j}$, the Chinese remainder theorem gives $\mathbb{Z}/n\mathbb{Z} \cong \prod_j \mathbb{Z}/p_j^{k_j}\mathbb{Z}$, and the roots of $f$ modulo $n$ are the CRT combinations of all tuples of roots modulo the $p_j^{k_j}$. Their number is the product of the numbers of roots modulo the prime powers, which is zero as soon as one factor is zero, and can be far larger than $\deg f$.

In $(\mathbb{Z}/n\mathbb{Z})[x]$ the multiplicity of a root $a$ is defined as the largest $e$ such that $(x - a)^e$ divides $f$; since $x - a$ is monic, divisibility holds modulo $n$ if and only if it holds modulo every $p_j^{k_j}$, so the multiplicity is the minimum of the multiplicities modulo the prime powers, and each of these is found by repeated exact division by $x - a$.

Use in FLINT#

gr_poly_roots_finite_field implements Algorithm 1 for every finite field context; step 4 is _gr_poly_factor_equal_deg_with_frob with $d = 1$, which also contains the Taylor shift trick. nmod_poly_roots and fmpz_mod_poly_roots wrap it and return the roots as linear factors in an nmod_poly_factor_t or fmpz_mod_poly_factor_t; the fq_*_poly_roots functions of fq_poly_factor and its variants are analogous, with the field arithmetic of Arithmetic in finite fields.

nmod_poly_roots_factored and fmpz_mod_poly_roots_factored take the factorisation of the modulus and implement the prime-power lifting and the CRT combination. They give up and return 0 when a list of roots would exceed about $2^{32}$ entries ($2^{25}$ on 32-bit systems); fmpz_mod_poly_roots_factored_with_length_limit takes the limit for the CRT combination as a parameter. The generic method gr_poly_roots over nmod and fmpz_mod contexts uses the finite field algorithm when the modulus is prime and otherwise factors the modulus and calls fmpz_mod_poly_roots_factored_with_length_limit with a limit of $10^6$ roots, returning GR_UNABLE if the modulus has more than 20 prime factors (with multiplicity) or there are too many roots.

Rational roots of integer polynomials (fmpz_poly_roots_fmpq) are found from the roots modulo a suitable prime by $p$-adic lifting, which is the same lifting as above for simple roots.

@misc{flint-doc-algorithms-polynomials-root-finding,
  author       = {{The FLINT team}},
  title        = {{Roots of polynomials over finite fields}},
  howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
  year         = {2026},
  url          = {https://flintlib.org/doc/algorithms/polynomials/root-finding.html},
  note         = {Generated 2026-11-02}
}