FLINT3.7.0-dev
/

fmpz_mod_poly_roots_factored, fmpz_mod_poly_roots_factored_with_length_limit

Synopsis#include <flint/fmpz_mod_poly_factor.h>
int fmpz_mod_poly_roots_factored(fmpz_mod_poly_factor_t r, const fmpz_mod_poly_t f, int with_multiplicity, const fmpz_factor_t n, const fmpz_mod_ctx_t ctx)source
int fmpz_mod_poly_roots_factored_with_length_limit(fmpz_mod_poly_factor_t x0, const fmpz_mod_poly_t f, int with_mult, slong length_limit, const fmpz_factor_t fac, const fmpz_mod_ctx_t ctx)source

Set the output to the linear factors x - a for the distinct roots a \in \mathbb{Z}/n\mathbb{Z} of the nonzero polynomial f, where the fmpz_factor_t holds the prime factorisation of the modulus n (not checked). If the multiplicity flag is nonzero, the exponent of x - a is the largest e such that (x - a)^e divides f in (\mathbb{Z}/n\mathbb{Z})[x], otherwise it is 1. Return 1 on success and 0 if the roots were not computed because there are too many of them. A zero f causes an exception.

The roots modulo each prime p \mid n are found with fmpz_mod_poly_roots (or are all residues if f \equiv 0 \bmod p), lifted to all roots modulo the prime power p^k \| n by Hensel lifting with doubling precision, and combined by the Chinese remainder theorem; see Roots modulo prime powers. The lists of roots modulo a prime power are limited to about 2^{32} entries (2^{25} on 32-bit systems), and the number of combined roots to the same bound for fmpz_mod_poly_roots_factored and to length_limit for fmpz_mod_poly_roots_factored_with_length_limit. If some prime power gives no root, the functions return 1 with no roots, even if another prime power has too many.

Cite this page

The FLINT team, “fmpz_mod_poly_roots_factored, fmpz_mod_poly_roots_factored_with_length_limit (fmpz_mod_poly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_mod_poly_factor/fmpz_mod_poly_roots_factored.html (generated 2026-10-20).