
A new black box factorization algorithm  the nonmonic case.Tian Chen, CECM, Simon Fraser UniveristyMonday July 17th, 10:30am, in AQ 5004. Abstract: 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 squarefree case. In this work, we contribute a new algorithm that also handles the nonmonic, nonsquarefree and nonprimitive 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. 