IMPROVED TECHNIQUES FOR FACTORING UNIVARIATE POLYNOMIALS

The paper describes improved techniques for factoring univariate polyn omials over the integers. The authors modify the usual linear method f or lifting modular polynomial factorizations so that efficient early f actor detection can be performed. The new lifting method is universall y faster than the classical quadratic method, and is faster than a lin ear method due to Wang, provided we lift; sufficiently high. Early fac tor detection is made more effective by also testing combinations of m odular factors, rather than just single modular factors. Various heuri stics are presented that reduce the cost of the factor testing or that increase the chance of successful testing. Both theoretical and empir ical computing times are presented. (C) 1996 Academic Press Limited