Multivariate Polynomial Factorization.

摘要

This paper describes algorithms for factoring a polynomial in one or more variables,with integer coefficients,into factors which are irreducible over the integers. These algorithms are based on the use of factorizations over finite fields and 'Hensel's Lemma construction'. 'Abstract algorithm'descriptions are used in the presentation of the underlying algebraic theory. Included is a new generalization of Hensel's p-adic construction which leads to a practical algorithm for factoring multivariate polynomials. The univariate case algorithm is also specified in greater detail than in the previous literature,with attention to a number of improvements which the author has developed based on theoretical computing time analyses and experience with actual implementations. (Author)