An Improved Multivariate Polynomial Factoring Algorithm
- 1 October 1978
- journal article
- Published by JSTOR in Mathematics of Computation
- Vol. 32 (144), 1215-1231
- https://doi.org/10.2307/2006346
Abstract
A new algorithm for factoring multivariate polynomials over the integers based on an algorithm by Wang and Rothschild is described. The new algorithm has improved strategies for dealing with the known problems of the original algorithm, namely, the leading coefficient problem, the bad-zero problem and the occurrence of extraneous factors. It has an algorithm for correctly predetermining leading coefficients of the factors. A new and efficient p-adic algorithm named EEZ is described. Basically it is a linearly convergent variable-by-variable parallel construction. The improved algorithm is generally faster and requires less store then the original algorithm. Machine examples with comparative timing are included.Keywords
This publication has 9 references indexed in Scilit:
- On the Efficiency of Algorithms for Polynomial FactoringMathematics of Computation, 1977
- Factoring Multivariate Polynomials over Algebraic Number FieldsMathematics of Computation, 1976
- Factoring Multivariate Polynomials Over the IntegersMathematics of Computation, 1975
- Multivariate Polynomial FactorizationJournal of the ACM, 1975
- An Inequality About Factors of PolynomialsMathematics of Computation, 1974
- Factoring Polynomials Over Large Finite FieldsMathematics of Computation, 1970
- The Art of Computer Programming. Vol. II: Seminumerical AlgorithmsMathematics of Computation, 1970
- On Hensel factorization, IJournal of Number Theory, 1969
- Factoring Polynomials Over Finite FieldsBell System Technical Journal, 1967