Description
When factoring the polynomial a + b + c + 5*a*d + 3*b*d + 4*c*d + 6*a*d^2 + 2*b*d^2 + 3*c*d^2 in Z, the method MultivariateFactorization#factorPrimitiveInZ0 uses Hensel lifting:
The values in the evaluation are chosen randomly, and when the values for the first (and only?) evaluation are [0, 0, 2] then lcRest will be set to null at the end of the second evaluation of the loop
for (int i = 0; i < lcFactors.length; i++) {
assert evaluation.evaluateFrom(biFactorsArrayMainZ[i].lc(0), 1).isConstant();
assert evaluation.evaluateFrom(lcFactors[i], 1).isConstant();
BigInteger
lcInMain = evaluation.evaluateFrom(biFactorsArrayMainZ[i].lc(0), 1).cc(),
lcTrue = evaluation.evaluateFrom(lcFactors[i], 1).cc();
if (!lcInMain.equals(lcTrue)) {
BigInteger
lcm = Rings.Z.lcm(lcInMain, lcTrue),
factorCorrection = lcm.divideExact(lcInMain),
lcCorrection = lcm.divideExact(lcTrue);
biFactorsArrayMainZ[i].multiply(factorCorrection);
//biFactorsCF = biFactorsCF.divideExact(factorCorrection);
lcFactors[i].multiply(lcCorrection);
lcRest = lcRest.divideOrNull(lcCorrection);
assert lcRest != null;
}
}where lcRest := 1 and lcCorrection := 3.
I have added a test case to demonstraten this behaviour at
https://github.com/algebrakit-org/rings/blob/e043cd5ed610c10f7c185d74af45cef4554bb675/rings/src/test/java/cc/redberry/rings/poly/multivar/HenselLiftingTest.java#L109-L129
I don't know enough about Hensel lifting and the algorithm used here (though it seems interesting!) to be able to estimate the failure rate, but given that this is the first time we ran into it in years while using your library extensively it seems like the failure rate is low. I guess that as a workaround we can probably just try the factorization again if it fails.