18.3. Classical recombination🔗

Classical Zassenhaus recombination enumerates subsets of the lifted factors. For each distinguished first factor it considers subsets in increasing cardinality, constructs the corresponding integer candidate, and tests exact division. The direct support-partition proof shows that the first accepted subset is exactly the support of the irreducible factor containing the distinguished modular factor.

This method has small overhead when the number of modular factors is small. Its worst-case subset search is exponential, so the public implementation uses a complete-level budget: it either finishes a whole subset-cardinality level or reports a typed decline before starting that level.

For a large modular support, the total factorizer first tries all unforced subsets of cardinality one through three. A factor found by exact division is peeled immediately; its exact quotient and the remaining lifted-factor indices are retained. This corrects an important weakness of a distinguished-first-factor search: a small integer factor need not contain the arbitrarily distinguished modular factor.