A polynomial reduction from multivariate to bivariate integral polynomial factorization.

ABSTRACT

Given an arbitrary but fixed integer r -&-ge; 3. We show that testing r-variate polynomials with integer coefficients for irreducibility is m-reducible in polynomial time of the total degree and the largest coefficient length to testing bivariate polynomials for irreducibility. Factoring r-variate polynomials into irreducibles is polynomial time Turing-reducible to completely factoring bivariate polynomials.

REFERENCES

• 1: Adleman, L. E., and Odlyzko, A. M., "Irreducibility testing and factorization of polynomials," in Proc. 22nd Symp. on Foundations of Comp. Sci., IEEE, Los Angeles 1981, 409-418.
• 2: Franz, W., "Untersuchungen zum Hilbertschen Irreduzibilit-&-auml;tssatz," Math. Zeitschrift 33 (1931), 275-293.
• 3: Gelfond, A. O., Transcendental and Algebraic Numbers, Dover Publ., N.Y. 1960.
• 4: Kaltofen, E., Musser, D. R., Saunders, B. D., "A generalized class of polynomials that are hard to factor," in {WANG81}.
• 5: Erich Leo Kaltofen, On the complexity of factoring polynomials with integer coefficients, 1982
• 6: Knuth, D. E., The Art of Programming, vol. 2, 2nd ed., Addison-Wesley, Reading, MA 1981.
• 7: Kronecker, L., "Grundz-&-uuml;ge einer arithmetischen Theorie der algebraischen Gr-&-ouml;ssen," J. f. reine und angew. Math. 92 (1882), 1-122.
• 8: David R. Musser, Multivariate Polynomial Factorization, Journal of the ACM (JACM), v.22 n.2, p.291-308, April 1975 [doi>10.1145/321879.321890]
• 9: van der Waerden, B. L., Einf-&-uuml;hrung in die algebraische Geometrie, Springer Verlag, Berlin 1939.
• 10: van der Waerden, B. L., Modern Algebra, vol. 1, trans. by F. Blum, Ungar Publ., N.Y. 1953.
• 11: Wang, P. S., "An improved multivariate polynomial factoring algorithm," Math. Comp. 32 (1978), 1215-1231.
• 12: Wang, P. S. (ed.), Proc. of the 1981 ACM Symp. on Symbolic and Algebraic Comp., ACM Baltimore, MD 1981.
• 13: David Y.Y. Yun, On square-free decomposition algorithms, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.26-35, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806320]
• 14: Richard Zippel, Newton's iteration and the sparse Hensel algorithm (Extended Abstract), Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.68-72, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806372]