On Checking Products of Modular Factors in Berlekamp-Hensel Type Factorization
Yasuhiro Tsukada, Tateaki Sasaki · 数式処理 · 2001
This article tests empirically two “dirty tricks” for the trial-division step of BerlekampHensel type algorithm for the univariate polynomial factorization over Z. The tricks are 1) divisibility check of the constant term and 2) boundedness check of the second coefficient. So far, it has been said that 1) is quite effective but 2) is not so effective. However, defining the upper bound of the second coefficient suitably, we show by many examples that the trick 2) is also quite effective for polynomials of medium and large degrees, such as degree ≥ 15.