An improved multivariate polynomial factoring algorithm
HTML articles powered by AMS MathViewer
- by Paul S. Wang PDF
- Math. Comp. 32 (1978), 1215-1231 Request permission
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
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 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 10.1002/j.1538-7305.1967.tb03174.x B. G. CLAYBROOK, "Factorization of multivariate polynomials over the integers," 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.
- 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, Inc.), New York-London, 1962. MR 0142550 MACSYMA Reference Manual, The MATHLAB Group, Project MAC, M.I.T., Cambridge, Mass., Nov. 1975.
- M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI 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 10.1090/S0025-5718-1977-0422193-8 J. MOSES & D. Y. Y. YUN, "The EZ-GCD algorithm," Proceedings of ACM Annual Conference, August 1973.
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 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 10.1090/S0025-5718-1976-0568283-X
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890 P. S. WANG, "Preserving sparseness in multivariate polynomial factorization," 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).
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X
Additional Information
- © Copyright 1978 American Mathematical Society
- 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