A new black box factorization algorithm - the non-monic case.

Tian Chen, CECM, Simon Fraser Univeristy

Monday July 17th, 10:30am, in AQ 5004.


Given a sparse polynomial a in Z[x1,...,xn] represented by a black box, we aim to find its factors in the sparse representation. The authors have previously developed an efficient algorithm for the monic and square-free case. In this work, we contribute a new algorithm that also handles the non-monic, non-square-free and non-primitive cases. We give a worst case complexity analysis with failure probabilities. The required number of probes to the black box in our algorithm is much less than the previously best known algorithm by Rubinfeld and Zippel in 1994. We have also implemented our new algorithm in Maple with all major subroutines in C. Our benchmarks show that our algorithm is much faster than the current best determinant and factorization algorithms in Maple and Magma.