FLINT3.7.0-dev
/

fmpz_poly_hensel_lift

Synopsis#include <flint/fmpz_poly.h>
void fmpz_poly_hensel_lift(fmpz_poly_t Gout, fmpz_poly_t Hout, fmpz_poly_t Aout, fmpz_poly_t Bout, const fmpz_poly_t f, const fmpz_poly_t g, const fmpz_poly_t h, const fmpz_poly_t a, const fmpz_poly_t b, const fmpz_t p, const fmpz_t p1)source

One Hensel step for a factorisation into two factors: given f \equiv gh and ag + bh \equiv 1 modulo p, with g and h monic, computes G \equiv g, H \equiv h, A \equiv a, B \equiv b modulo p with f \equiv GH and AG + BH \equiv 1 modulo P = p p_1:

\begin{aligned} G &= g + p \left( \tfrac{f - gh}{p}\, b \bmod g \right), & H &= h + p \left( \tfrac{f - gh}{p}\, a \bmod h \right), \\ B &= b + p \left( \tfrac{1 - aG - bH}{p}\, b \bmod g \right), & A &= a + p \left( \tfrac{1 - aG - bH}{p}\, a \bmod h \right), \end{aligned}

with the products reduced modulo p_1. Requires 1 < p_1 \le p (so p_1 \mid p for prime powers of the same prime), f, g, h of degree at least 1, and a, b nonzero. The outputs G, H, A, B may be aliased only with g, h, a, b respectively.

Cite this page

The FLINT team, “fmpz_poly_hensel_lift (fmpz_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/fmpz_poly/fmpz_poly_hensel_lift.html (generated 2026-10-20).