nmod_poly_factor_distinct_deg, nmod_poly_factor_distinct_deg_threaded
#include <flint/nmod_poly_factor.h>void nmod_poly_factor_distinct_deg(nmod_poly_factor_t res, const nmod_poly_t poly, slong * const * degs)sourcevoid nmod_poly_factor_distinct_deg_threaded(nmod_poly_factor_t res, const nmod_poly_t poly, slong * const * degs)sourceDistinct-degree factorisation of a squarefree polynomial poly of degree at least 1, which need not be monic. Appends to res monic polynomials f_1, \ldots, f_k, each with exponent 1, such that f_j is the product of all monic irreducible factors of poly of one degree d_j, and writes d_j to (*degs)[j - 1]. The array *degs must have room for \deg(\mathit{poly}) entries; the d_j are distinct but not sorted. If poly is not squarefree the output is meaningless.
This is gr_poly_factor_distinct_deg, the baby-step giant-step algorithm of Kaltofen and Shoup with Brent–Kung modular composition [KalSho1998]; see Distinct-degree factorisation. It uses several threads by itself when they are available, so nmod_poly_factor_distinct_deg_threaded is now an alias of nmod_poly_factor_distinct_deg. A constant poly causes an exception.
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, “nmod_poly_factor_distinct_deg, nmod_poly_factor_distinct_deg_threaded (nmod_poly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/nmod_poly_factor/nmod_poly_factor_distinct_deg.html (generated 2026-10-20).
@misc{flint-doc-nmod-poly-factor-nmod-poly-factor-distinct-deg,
author = {{The FLINT team}},
title = {{nmod\_poly\_factor\_distinct\_deg, nmod\_poly\_factor\_distinct\_deg\_threaded (nmod\_poly\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/nmod_poly_factor/nmod_poly_factor_distinct_deg.html},
note = {Generated 2026-10-20}
}