Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [1] E. R. BERLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713-735. MR 43 #1948. MR 0276200 (43:1948)
  • [2] E. R. BERLEKAMP, "Factoring polynomials over finite fields," Bell System Tech. J., v. 46, 1967, pp. 1853-1859. MR 36 #2314. MR 0219231 (36:2314)
  • [3] B. G. CLAYBROOK, "Factorization of multivariate polynomials over the integers," SIGSAM Bulletin, Feb. 1976, p. 13.
  • [4] J. H. GRIESMER, D. R. JENKS & D. Y. Y. YUN, SCRATCHPAD User's Manual, IBM Research Report, RA 70, June 1975.
  • [5] D. E. KNUTH, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
  • [6] S. LANG, Diophantine Geometry, Wiley, New York, 1962. MR 0142550 (26:119)
  • [7] MACSYMA Reference Manual, The MATHLAB Group, Project MAC, M.I.T., Cambridge, Mass., Nov. 1975.
  • [8] M. MIGNOTTE, "An inequality about factors of polynomials," Math. Comp., v. 28, 1974, pp. 1153-1157. MR 0354624 (50:7102)
  • [9] R. T. MOENCK, "On the efficiency of algorithms for polynomial factoring," Math. Comp., v. 31, 1977, pp. 235-250. MR 0422193 (54:10185)
  • [10] J. MOSES & D. Y. Y. YUN, "The EZ-GCD algorithm," Proceedings of ACM Annual Conference, August 1973.
  • [11] D. R. MUSSER, "Multivariate polynomial factorization," J. Assoc. Comput. Mach., v. 22, 1975, pp. 291-308. MR 0396470 (53:335a)
  • [12] P. S. WANG, "Factoring multivariate polynomials over algebraic number fields," Math. Comp., v. 30, 1976, pp. 324-336. MR 0568283 (58:27887a)
  • [13] P. S. WANG & L. P. ROTHSCHILD, "Factoring multivariate polynomials over the integers," Math. Comp., v. 29, 1975, pp. 935-950. MR 0396471 (53:335b)
  • [14] P. S. WANG, "Preserving sparseness in multivariate polynomial factorization," Proceedings, MACSYMA User's Conference, University of California at Berkeley, July 27-29, 1977.
  • [15] 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).
  • [16] H. ZASSENHAUS, "On Hensel factorization. I," J. Number Theory, v. 1, 1969, pp. 291-311. MR 39 #4120. MR 0242793 (39:4120)

Similar Articles

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

Retrieve articles in all journals with MSC: 12-04


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1978-0568284-3
Article copyright: © Copyright 1978 American Mathematical Society

American Mathematical Society