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≡ghf \equiv gh and ag+bh≡1ag + bh \equiv 1 modulo pp, with gg and hh monic, computes G≡gG \equiv g, H≡hH \equiv h, A≡aA \equiv a, B≡bB \equiv b modulo pp with f≡GHf \equiv GH and AG+BH≡1AG + BH \equiv 1 modulo P=pp1P = p p_1:

G=g+p(f−ghp b mod g),H=h+p(f−ghp a mod h),B=b+p(1−aG−bHp b mod g),A=a+p(1−aG−bHp a mod h),\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 p1p_1. Requires 1<p1≤p1 < p_1 \le p (so p1∣pp_1 \mid p for prime powers of the same prime), f,g,hf, g, h of degree at least 1, and a,ba, b nonzero. The outputs G,H,A,BG, H, A, B may be aliased only with g,h,a,bg, 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-11-02).