18.5. Logarithmic derivatives and lattice recombination🔗

For larger modular factorizations, Hex uses the recombination method of Belabas, van Hoeij, Klüners, and Steel. For a lifted local factor g, form its combined logarithmic derivative (CLD), Φ(g) = f · g' / g mod p^a.

The identity Φ(gh) = Φ(g) + Φ(h) changes multiplication of selected factors into addition of coefficient vectors. These vectors form the coefficient block of an integer lattice. LLL reduction finds short relations, and projection to the first coordinates produces zero-one support indicators.

The Belabas-Hoeij-Klüners-Steel (BHKS) argument has two inclusions. At the coefficient-recovery precision, every genuine factor support indicator lies in the projected span. At the resultant precision, every retained short vector is constant on genuine supports. The two spans are then equal, so the equivalence classes of projected columns are exactly the irreducible-factor supports.

This lattice calculation determines which lifted factors belong together; it is not the older LLL polynomial-factorization algorithm that recovers a factor directly from one short vector.