Multivariate Polynomial Factorization
David R. Musser · Journal of the ACM · 1975
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 factorIzatmns over finite fields and "Hensel's lemma constructions " "Abstract algorithm" descripttons are used m the presentation of the underlying algebra:c theory Included ~s a new generahzatmn of Hensel's p-adlc constructmn which leads to a practical algorithm for factorlng multivariate polynommls The univarmte case algorithm is also specified m greater deta:l than in the prewous literature, with attentmn to a number of improvements wh:ch the author has developed based OR theoretical computing time analyses and experience with actual implementatmns
Cited by 102 works. doi:10.1145/321879.321890 Open-access PDF
Authors
References
- The Art of Computer Programming
- Algebraic Coding Theory
- On Hensel factorization, I
- An Inequality About Factors of Polynomials
- Computable Algebra, General Theory and Theory of Computable Fields
- Algorithms for polynomial factorization.
- Computer Algebra of Polynomials and Rational Functions
- Allocating Storage for Extendible Arrays
- The SAC-1 system
- The SAC-1 Modular Arithmetic System