gr_poly_factor_distinct_deg, _gr_poly_factor_distinct_deg_with_frob, _gr_poly_factor_distinct_deg_with_frob_threaded
#include <flint/gr_poly.h>int gr_poly_factor_distinct_deg(gr_poly_vec_t fac, fmpz_vec_t degs, const gr_poly_t poly, gr_ctx_t ctx)sourceint _gr_poly_factor_distinct_deg_with_frob(gr_poly_vec_t fac, fmpz_vec_t degs, const gr_poly_t poly, const gr_poly_preinv_t P, const gr_poly_t frob, const fmpz_t q, gr_ctx_t ctx)sourceint _gr_poly_factor_distinct_deg_with_frob_threaded(gr_poly_vec_t fac, fmpz_vec_t degs, const gr_poly_t poly, const gr_poly_preinv_t P, const gr_poly_t frob, const fmpz_t q, gr_ctx_t ctx)sourceCompute the distinct-degree factorisation of a squarefree polynomial: \operatorname{monic}(f) = \prod_i g_i, where g_i is the product of the irreducible factors of degree d_i and the d_i are distinct. The g_i are written to fac and the d_i to degs. The result is undefined if f is not squarefree.
This is the baby-step giant-step algorithm of Kaltofen and Shoup [KalSho1998], with the baby steps computed by _gr_poly_iterated_frobenius_preinv and the giant steps by modular composition with a precomputed matrix. The underscore versions assume f monic, take the precomputed modulus P for f, x^q \bmod f as frob and q, and append to fac and degs. The factorisation functions choose the sparse representation of the modulus automatically when it applies (gr_poly_preinv_set), so sparse inputs benefit from cheap reductions.
When more than one thread is available (flint_set_num_threads) and the ring is thread-safe (gr_ctx_is_threadsafe), the threaded variant is used: the giant steps are computed in blocks of independent compositions sharing one precomputed matrix, the interval polynomials of a block and the splitting of the intervals are computed in parallel, and the vector Brent-Kung composition of the baby steps evaluates its polynomials in parallel. Matrix products are done outside the parallel sections, so that gr_mat_mul can use threads itself. The total work exceeds that of the serial algorithm by a few percent.
References#
- [KalSho1998] E. Kaltofen and V. Shoup, "Subquadratic-time factoring of polynomials over finite fields", Mathematics of Computation 67 (1998), 1179-1197. https://doi.org/10.1090/S0025-5718-98-00944-2
The FLINT team, “gr_poly_factor_distinct_deg, _gr_poly_factor_distinct_deg_with_frob, _gr_poly_factor_distinct_deg_with_frob_threaded (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/gr_poly_factor_distinct_deg.html (generated 2026-10-20).
@misc{flint-doc-gr-poly-gr-poly-factor-distinct-deg,
author = {{The FLINT team}},
title = {{gr\_poly\_factor\_distinct\_deg, \_gr\_poly\_factor\_distinct\_deg\_with\_frob, \_gr\_poly\_factor\_distinct\_deg\_with\_frob\_threaded (gr\_poly.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/gr_poly/gr_poly_factor_distinct_deg.html},
note = {Generated 2026-10-20}
}