fmpz_poly_factor_van_hoeij
Synopsis
#include <flint/fmpz_poly_factor.h>void fmpz_poly_factor_van_hoeij(fmpz_poly_factor_t final_fac, const nmod_poly_factor_t fac, const fmpz_poly_t f, slong exp, ulong p)sourceAppends the irreducible factors of the squarefree primitive f, each with multiplicity exp, to final_fac, given its factorisation fac into r \ge 2 monic irreducible factors modulo the prime p, by van Hoeij's knapsack algorithm with gradual feeding of CLD data [vHo2002], [HvHN2011]. The modular factors are lifted to an initial precision, a lattice is reduced with LLL after each new column of CLD data, and the precision is doubled until a 0-1 basis of the recombination lattice is found and verified.
References#
- [vHo2002] M. van Hoeij. Factoring polynomials and the knapsack problem. Journal of Number Theory 95 (2002), 167–189. https://doi.org/10.1006/jnth.2001.2763
- [HvHN2011] W. Hart, M. van Hoeij and A. Novocin. Practical polynomial factoring in polynomial time. ISSAC 2011, 163–170. https://doi.org/10.1145/1993886.1993915
Cite this page
The FLINT team, “fmpz_poly_factor_van_hoeij (fmpz_poly_factor.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly_factor/fmpz_poly_factor_van_hoeij.html (generated 2026-10-20).
@misc{flint-doc-fmpz-poly-factor-fmpz-poly-factor-van-hoeij,
author = {{The FLINT team}},
title = {{fmpz\_poly\_factor\_van\_hoeij (fmpz\_poly\_factor.h)}},
howpublished = {FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev},
year = {2026},
url = {https://flintlib.org/doc/fmpz_poly_factor/fmpz_poly_factor_van_hoeij.html},
note = {Generated 2026-10-20}
}