FLINT3.7.0-dev
/

gr_poly_factor_distinct_deg, _gr_poly_factor_distinct_deg_with_frob, _gr_poly_factor_distinct_deg_with_frob_threaded

Synopsis#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)source
int _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)source
int _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)source

Compute the distinct-degree factorisation of a squarefree polynomial: monic⁡(f)=∏igi\operatorname{monic}(f) = \prod_i g_i, where gig_i is the product of the irreducible factors of degree did_i and the did_i are distinct. The gig_i are written to fac and the did_i to degs. The result is undefined if ff 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 ff monic, take the precomputed modulus P for ff, xq mod fx^q \bmod f as frob and qq, 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#

Cite this page

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-11-02).