Factoring multivariate polynomials over the integers

ABSTRACT

This paper gives an algorithm for finding the irreducible factors of any multivariate polynomial with integer coefficients. The algorithm begins by making substitutions for all but one of the variable. This univariate polynomial is then factored by a known method, which uses an algorithm of Berlekamp for factoring univariate polynomials over finite fields. After this factorization is done, the multivariate factors are recovered from the univariate ones by a kind of Hensel algorithm. A number of ideas are given which greatly speed the computation in some special cases.

REFERENCES

• 1: Berlekamp, E. R., "Factoring polynomials over finite fields", <u>Bell System Technological Journal</u>, Vol. 46, 1967, p p. 1853--1859.
• 2: Berlekamp, E. R., "Factoring polynomials over large finite fields", <u>Mathematics of Computation</u>, July, 1970.
• 3: W. S. Brown, On Euclid's Algorithm and the Computation of Polynomial Greatest Common Divisors, Journal of the ACM (JACM), v.18 n.4, p.478-504, Oct. 1971 [doi>10.1145/321662.321664]
• 4: Collins, G. E., "SAC-1 Modular Arithmetic Systems", University of Wisconsin Technical Report #10, June, 1969.
• 5: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 6: W. A. Martin , R. J. Fateman, The MACSYMA system, Proceedings of the second ACM symposium on Symbolic and algebraic manipulation, p.59-75, March 23-25, 1971, Los Angeles, California, United States [doi>10.1145/800204.806267]
• 7: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 8: David Rea Musser, Algorithms for polynomial factorization., 1971
• 9: Van der Waerden, B. L., <u>Modern Algebra</u>, Vol. 1, Frederick Ungar Publishing Company, New York, 1953.
• 10: Zassenhaus, H., "On Hensel Factorization I", Journal of Number Theory, Vol. 1, 1969, pp. 291--311.