A fast implementation of polynomial factorization

Abstract

A xw pAage fat fac~oriirg polynomials with integer coeficients is described which yields signant improvements over previous implementations in both time and space requirements. For multivariate problems, the package features an inexpensive method for early detection and correction of spurious factors. This essentially solves the multivariate extraneous factor problem and eliminates the need to factor mom than one univariate image, except in rare cases. Also included is an improved technique for coe5cient prediction which is successful mom frequently than prior versions at short-circuiting the expensive multivariate Hensel lifting stage. In addition some new approaches are discussed for the univariate case as well as for the problem of finding good integer substitution values. The package has been implemented both in Scratchpad II and in an experimental version of muMATH.