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.