13.4. Iterative and multifactor lifts🔗

Hex.ZPoly.henselLift iterates the linear step to lift a single two-factor split all the way from modulus p to p^k.

def

Hex.ZPoly.henselLift (p k : ℕ) [Hex.ZMod64.Bounds p] (f g h : Hex.ZPoly)
  (s t : Hex.FpPoly p) : Hex.LinearLiftResult
Hex.ZPoly.henselLift (p k : ℕ)
  [Hex.ZMod64.Bounds p]
  (f g h : Hex.ZPoly)
  (s t : Hex.FpPoly p) :
  Hex.LinearLiftResult

Lift a factorization modulo p to a factorization modulo p^k by iterating the linear Hensel step.

Factorization pipelines need to lift an ordered list of mod-p factors simultaneously, not just a single split. The multifactor API does this by a sequential binary split tree: at each node it lifts the first factor against the product of the rest, then recurses. There are linear and quadratic-doubling versions. The factorization pipeline uses the quadratic one, because of its O(log k) precision growth.

def

Hex.ZPoly.multifactorLift (p k : ℕ) [Hex.ZMod64.Bounds p]
  (f : Hex.ZPoly) (factors : Array Hex.ZPoly) : Array Hex.ZPoly
Hex.ZPoly.multifactorLift (p k : ℕ)
  [Hex.ZMod64.Bounds p] (f : Hex.ZPoly)
  (factors : Array Hex.ZPoly) :
  Array Hex.ZPoly

Lift an ordered array of factors from congruence modulo p to congruence modulo p^k.

def

Hex.ZPoly.multifactorLiftQuadratic (p k : ℕ) [Hex.ZMod64.Bounds p]
  (f : Hex.ZPoly) (factors : Array Hex.ZPoly) : Array Hex.ZPoly
Hex.ZPoly.multifactorLiftQuadratic
  (p k : ℕ) [Hex.ZMod64.Bounds p]
  (f : Hex.ZPoly)
  (factors : Array Hex.ZPoly) :
  Array Hex.ZPoly

Quadratic multifactor Hensel lift.

Lifts an ordered array of factors of f from congruence modulo p to congruence modulo p^k using the doubling step quadraticHenselStep inside the same sequential split tree as multifactorLift.