18.1. From integer factors to modular factors🔗

HexBerlekampZassenhaus factors dense univariate polynomials over the integers. The public function Hex.ZPoly.factorize first separates the signed content, powers of X, and repeated factors. The remaining polynomial is primitive, square-free, and has positive leading coefficient.

For a suitable prime p, reduction modulo p preserves the square-free factorization. Hex factors the resulting polynomial over 𝔽_p by Berlekamp's method, then uses Hensel lifting to raise the modular factors from p to a sufficiently large power p^a. Each irreducible integer factor is represented by a product of some of these lifted factors. Determining those subsets is called recombination.