CECM Home > Events > CECM Annual Summer Meeting 2005 > Program > Poster Abstract: Al Erickson
Poster Abstract
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.