An improved multivariate polynomial factoring algorithm

Wang, Paul S.

doi:10.1090/S0025-5718-1978-0568284-3

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
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.

[1] E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 0276200 (43 #1948), http://dx.doi.org/10.1090/S0025-5718-1970-0276200-X
[2] E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. 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] 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 (44 #3531)
[6] 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 (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. 28 (1974), 1153–1157. MR 0354624 (50 #7102), http://dx.doi.org/10.1090/S0025-5718-1974-0354624-3
[9] Robert T. Moenck, On the efficiency of algorithms for polynomial factoring, Math. Comp. 31 (1977), no. 137, 235–250. MR 0422193 (54 #10185), http://dx.doi.org/10.1090/S0025-5718-1977-0422193-8
[10] J. MOSES & D. Y. Y. YUN, "The EZ-GCD algorithm," Proceedings of ACM Annual Conference, August 1973.
[11] David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 0396470 (53 #335a)
[12] Paul S. Wang, Factoring multivariate polynomials over algebraic number fields, Math. Comp. 30 (1976), no. 134, 324–336. MR 0568283 (58 #27887a), http://dx.doi.org/10.1090/S0025-5718-1976-0568283-X
[13] Paul S. Wang and Linda Preiss Rothschild, Factoring multivariate polynomials over the integers, Math. Comput. 29 (1975), 935–950. MR 0396471 (53 #335b), http://dx.doi.org/10.1090/S0025-5718-1975-0396471-3
[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] Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 0242793 (39 #4120)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|