Hensel lifting

also: hensel, lifting, zassenhaus

Turning a factorization modulo p into one modulo p^k, one power at a time. The step is exact linear algebra rather than a search: the error divided by p^k fixes what the correction must be, and the Bezout relation between the two mod-p factors solves for it directly.

Turn a factorization modulo $p$ into one modulo $p^{k}$ , one power at a time. The step is exact linear algebra, not a search.

Suppose $f \equiv g h (mod p^{k})$ . Write the error as $f - g h = p^{k} c$ . A correction $g + p^{k} u$ , $h + p^{k} v$ changes the product by $p^{k} (u h + v g)$ modulo $p^{k + 1}$ , so the requirement is

u h_{1} + v g_{1} \equiv c (mod p)

which the Bezout relation $s g_{1} + t h_{1} \equiv 1$ solves outright: take $u = t c$ and $v = sc$ , then reduce $u$ modulo $g_{1}$ to keep the degrees from drifting, moving the compensating multiple of $h_{1}$ into $v$ .

One step.

let hensel_step p m f g h g1 h1 s t =
  let err = Upoly.sub f (Upoly.mul g h) in
  let c = Upoly.divexact_int err m in
  let cp = Upoly.to_fp c p in
  let u0 = Fp.rem p (Fp.mul p t cp) g1 in
  let q  = Fp.div p (Fp.mul p t cp) g1 in
  let v0 = Fp.add p (Fp.mul p s cp) (Fp.mul p q h1) in
  (Upoly.add g (Upoly.scale (Upoly.of_fp u0 p) m),
   Upoly.add h (Upoly.scale (Upoly.of_fp v0 p) m))

The precondition is that the two mod- $p$ factors are coprime, which is why the prime is chosen to keep the input square-free. Lift far enough, past twice the Landau-Mignotte bound, and the symmetric representatives are the integer factors rather than merely congruent to them.