Л new package foi faaoriiig polynomials with integer coefficients is described which yields significant 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 more than one univariate image, except in rare cases. Also included is an improved technique for coefficient prediction which is successful more 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.
Introduction
Paul Wang's EEZ algorithm [8] is probably the most efficient method to have been implemented in computer algebra systems for factoring multivariate polynomials with integer coefficients. Versions similar to Wang's original presentation currently exist in MACSYMA, REDUCE (see [2]), Scratchpad I and Scratchpad II. The algorithm accepts a squarefree multivariate polynomial U(xl,x2,~- ,x„) as input which is then reduced to a univariate polynomial U(£x1, a2,..., a„) via the substitution of suitable random integers a2, a2,..., a„ for x2, x2,..., x„. U0 is factored using a separate technique and then a p-adic iteration (Hensel lifting) is employed to construct the multivariate factors from their univariate images. The factors are lifted in a variable-by-variable fashion and each variable is lifted degree-by-degree. The algorithm features a clever method by which the leading coefficients of the factors may be predetermined. This technique solves the so-called leading coefficient problem which was an obstacle in earlier factorization algorithms, such as [9]. Furthermore, it provides the opportunity to predict additional coefficients if the polynomial is sparse enough, as described below.
Coefficient Prediction
Wang demonstrates that if the factors of a multivariate polynomial are sufficiently sparse relative to one another (i.e. if there are not too many occurrences of terms having the same degrees in the same variables), then some of the coefficients of the factors may be predetermined without any p-adic lifting, given a factorization reduced modulo some polynomial ideal and given the true multivariate leading coefficients of each of the factors. This procedure, which is invoked prior to the lifting of each variable, is of great importance since it is often successful at obtaining a complete factorization without further p-adic lifting. The technique as described in [8], however, is limited in two ways. First, it extracts information only from terms in the input polynomial that arise as a single product of terms from the factors; terms which arise as the sum of two or more products are not considered. Second, if there are more than two factors, the factor list is split into two parts and the technique is applied recursively. The success of the procedure
Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specfic permission.
