Factorization over finitely generated fields

ABSTRACT

This paper considers the problem of factoring polynomials over a variety of domains. We first describe the current methods of factoring polynomials over the integers, and extend them to the integers mod p. We then consider the problem of factoring over algebraic domains. Having produced several negative results, showing that, if the domain is not properly specified, then the problem is insoluble, we then show that, for a properly specified finitely generated extension of the rationals or the integers mod p, the problem is soluble. We conclude by discussing the problems of factoring over algebraic closures.

REFERENCES

• 1: Berlekamp, E.R., Factoring Polynomials over Finite Fields. Bell System Tech. J. 46(1967) pp. 1853-1859.
• 2: Berlekamp, E.R., Factoring Polynomials over Large Finite Fields. Math. Comp. 24 (1970) pp. 713-735.
• 3: George E. Collins, Factoring univariate integral polynomial in polynomial average time, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.317-329, June 01, 1979
• 4: Davenport, J.H., On the Integration of Algebraic Functions. Springer Lecture Notes in Computer Science 102, Springer-Verlag, Berlin-Heidelberg-New York, 1981.
• 5: Endler, O., Konstruktion von allgemeinen Normalkörpen in beschränkt vielen Schritten. Hausdorff-Gedächtnis-Preisarbeit der Math.-Nat.-Fakultät Bonn 1952.
• 6: Fröhlich, A. & Shepherdson, J.C., Effective Procedures in Field Theory. Phil. Trans. Roy. Soc. Ser. A 248(1955-6) pp. 407-432.
• 7: Kleene, S.C., On Notation of Ordinal Numbers. Journal of Symbolic Logic 3(1938) pp. 150-155.
• 8: Krull, W., Uber Polynomzerlegung mit endlich vielen Schritten. Math. Z. 59(1953) pp. 57-60.
• 9: P. M. A. Moore , A. C. Norman, Implementing a polynomial factorization and GCD package, Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.109-116, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806379]
• 10: David Rea Musser, Algorithms for polynomial factorization., 1971
• 11: Risch, R.H., The Problem of Integration in Finite Terms. Trans. A.M.S. 139(1969) pp. 167-189 (MR 38 #5759).
• 12: Barry M. Trager, Algebraic factoring and rational function integration, Proceedings of the third ACM symposium on Symbolic and algebraic computation, p.219-226, August 10-12, 1976, Yorktown Heights, New York, United States [doi>10.1145/800205.806338]
• 13: Trager, B.M., Integration of Algebraic Functions. Ph.D. Thesis, M.I.T. Dept. of EE & CS, expected date Sept. 1981.
• 14: van der Waerden, B.L., Modern Algebra, Frederick Ungar, New York, 1949 (Translated from Moderne Algebra 2nd. ed.).
• 15: Wang, P.S., Factoring Multivariate Polynomials over Algebraic Number Fields. Math. Comp. 30(1976) pp. 324-336.
• 16: Wang, P.S., An Improved Multivariable Polynomial Factorising Algorithm. Math. Comp. 32(1978) pp. 1215-1231.
• 17: Wang, P.S. & Rothschild, L.P., Factoring Multi-Variate Polynomials over the Integers. Math. Comp. 29(1975) pp. 935-950.
• 18: P. J. Weinberger , L. P. Rothschild, Factoring Polynomials Over Algebraic Number Fields, ACM Transactions on Mathematical Software (TOMS), v.2 n.4, p.335-350, Dec. 1976 [doi>10.1145/355705.355709]
• 19: Yun, D.Y.Y., On the Equivalence of Polynomial Gcd and Squarefree Factorization Algorithms. Proc. 1977 MACSYMA Users' Conference {NASA publication CP-2012, National Technical Information Service, Springfield, Virginia}, pp. 65-70.
• 20: Zassenhaus, H., On Hensel Factorization. I. J. Number Theory 1 (1969) pp. 291-311. MR 39 #4120.
• 21: Zassenhaus, H., Polynomial time factoring of integer polynomials. Presentation to Symbolic Mathematics Committee of SHARE Europe Association, Antwerp, 15th. Jan 1981. {An earlier version of this, entitled "On a problem of Collins", was presented at the AMS Summer Meeting in Ann Arbor, Aug. 1980.}
• 22: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

General Terms:
Algorithms, Theory