Text Size: ππππ

CECM Home > Events > CECM Annual Summer Meeting 2005 > Program > Poster Abstract: Al Erickson

CECM 05 Home Registration Poster Session Social Event Program Participants Photo Gallery

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.