Symbolic factoring of polynomials in several variables

ABSTRACT

An algorithm for finding the symbolic factors of a multivariate polynomial with integer coefficients is presented. The algorithm is an extension of a technique used by Kronecker in a proof that the prime factoring of any polynomial may be found in a finite number of steps. The algorithm consists of factoring single-variable instances of the given polynomial by Kronecker's method and introducing the remaining variables by interpolation. Techniques for implementing the algorithm and several examples are discussed. The algorithm promises sufficient power to be used efficiently in an online system for symbolic mathematics.

REFERENCES

• 1: CLAPP, L. C. AND KAIN, R.Y. A computer aid for symbolic mathematics. Proc. AFIPS 1963 Fall Joint Comput. Conf., Spartan Books, Washington, D. C., 1963, pp. 509-517.
• 2: ENGELMAN, C. MATHLAB: a program for on-line machine assistance in symbolic computations. Proc. AFIPS 1965 Fall Joint Comput. Conf., Spartan Books, Washington, D. C., 1965, pp. 413-421.
• 3: VAN DER WAERDEN, B. L. Modern Algebra, Vol. 1. Ungar Publishing Co., New York, 1953.
• 4: JOHNSON, S.C. A factoring algorithm for polynomials over an arbitrary Galois extension of the rationals. Bell Telephone Lab., unpublished paper.
• 5: BIRKHOFF, G., AND MACLANE, S. A Survey of Modern Algebra. Macmillan, New York, 1953.
• 6: JOHNSON, S.C. Tricks for improving Kronecker's polynomial factoring algorithm. Bell Telephone Lab., unpublished paper.
• 7: BEREZIN, I. S., AND ZHIDKOV, N.P. Computing Methods, Vol. 1. Addison Wesley, Reading, Mass., and Pergamon Press, New York, 1965.