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.