Multivariate Polynomial Factorization
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1974
- Accession Number
- AD0787732
Entities
People
- David R. Musser
Organizations
- University of Wisconsin–Madison