An improved multivariate polynomial factoring algorithm

Author:
Paul S. Wang

Journal:
Math. Comp. **32** (1978), 1215-1231

MSC:
Primary 12-04

DOI:
https://doi.org/10.1090/S0025-5718-1978-0568284-3

MathSciNet review:
0568284

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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.

- E. R. Berlekamp,
*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**276200**, DOI https://doi.org/10.1090/S0025-5718-1970-0276200-X - E. R. Berlekamp,
*Factoring polynomials over finite fields*, Bell System Tech. J.**46**(1967), 1853–1859. MR**219231**, DOI https://doi.org/10.1002/j.1538-7305.1967.tb03174.x
B. G. CLAYBROOK, "Factorization of multivariate polynomials over the integers," - Donald E. Knuth,
*The art of computer programming. Vol. 2: Seminumerical algorithms*, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969. MR**0286318** - Serge Lang,
*Diophantine geometry*, Interscience Tracts in Pure and Applied Mathematics, No. 11, Interscience Publishers (a division of John Wiley & Sons), New York-London, 1962. MR**0142550**
MACSYMA Reference Manual, - M. Mignotte,
*An inequality about factors of polynomials*, Math. Comp.**28**(1974), 1153–1157. MR**354624**, DOI https://doi.org/10.1090/S0025-5718-1974-0354624-3 - Robert T. Moenck,
*On the efficiency of algorithms for polynomial factoring*, Math. Comp.**31**(1977), no. 137, 235–250. MR**422193**, DOI https://doi.org/10.1090/S0025-5718-1977-0422193-8
J. MOSES & D. Y. Y. YUN, "The EZ-GCD algorithm," - David R. Musser,
*Multivariate polynomial factorization*, J. Assoc. Comput. Mach.**22**(1975), 291–308. MR**396470**, DOI https://doi.org/10.1145/321879.321890 - Paul S. Wang,
*Factoring multivariate polynomials over algebraic number fields*, Math. Comp.**30**(1976), no. 134, 324–336. MR**568283**, DOI https://doi.org/10.1090/S0025-5718-1976-0568283-X - David R. Musser,
*Multivariate polynomial factorization*, J. Assoc. Comput. Mach.**22**(1975), 291–308. MR**396470**, DOI https://doi.org/10.1145/321879.321890
P. S. WANG, "Preserving sparseness in multivariate polynomial factorization," - Hans Zassenhaus,
*On Hensel factorization. I*, J. Number Theory**1**(1969), 291–311. MR**242793**, DOI https://doi.org/10.1016/0022-314X%2869%2990047-X

*SIGSAM Bulletin*, Feb. 1976, p. 13. J. H. GRIESMER, D. R. JENKS & D. Y. Y. YUN,

*SCRATCHPAD User’s Manual*, IBM Research Report, RA 70, June 1975.

*The MATHLAB Group*, Project MAC, M.I.T., Cambridge, Mass., Nov. 1975.

*Proceedings of ACM Annual Conference*, August 1973.

*Proceedings, MACSYMA User’s Conference*, University of California at Berkeley, July 27-29, 1977. D. Y. Y. YUN,

*The Hensel Lemma in Algebraic Manipulation*, Ph. D. Thesis, Department of Mathematics, M.I.T., Nov. 1973 (also Project MAC TR-138, Nov. 1974).

Retrieve articles in *Mathematics of Computation*
with MSC:
12-04

Retrieve articles in all journals with MSC: 12-04

Additional Information

Article copyright:
© Copyright 1978
American Mathematical Society