Univariate Polynomial Factorization in Maple via Combinatorial Trial Division
Al Erickson, Michael Monagan and Ha Le
We present Maple implementation for polynomial factorization in Z [x].
The implementation uses "recden", a recursive dense polynomial representation. The algorithm uses the Cantor Zanssenhaus/Distinct Degree or Belekamp's big prime algorithm followed by a quadratic parallel Hensel lift with trial division of combinations of 1 and 2 modular factors at each step. The algorithm finishes with a combinatorial algorithm, checking the necessary combinations of lifted factors to find real factors. We will also show a bivariate version of the Hensel lift.