Factoring multivariate polynomials over algebraic number fields
HTML articles powered by AMS MathViewer
- by Paul S. Wang PDF
- Math. Comp. 30 (1976), 324-336 Request permission
Abstract:
The algorithm for factoring polynomials over the integers by Wang and Rothschild is generalized to an algorithm for the irreducible factorization of multivariate polynomials over any given algebraic number field. The extended method makes use of recent ideas in factoring univariate polynomials over large finite fields due to Berlekamp and Zassenhaus. The procedure described has been implemented in the algebraic manipulation system MACSYMA. $^{\ast \ast }$ Some machine examples with timing are included.References
- E. R. Berlekamp, Factoring polynomials over large finite fields, Math. Comp. 24 (1970), 713–735. MR 276200, DOI 10.1090/S0025-5718-1970-0276200-X
- E. R. Berlekamp, Factoring polynomials over finite fields, Bell System Tech. J. 46 (1967), 1853–1859. MR 219231, DOI 10.1002/j.1538-7305.1967.tb03174.x
- 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
- M. Mignotte, An inequality about factors of polynomials, Math. Comp. 28 (1974), 1153–1157. MR 354624, DOI 10.1090/S0025-5718-1974-0354624-3 D. A. MOON, MACLISP Reference Manual, Project MAC, M.I.T., Cambridge, Mass., April 1974.
- Joel Moses, Symbolic integration: The stormy decade, Comm. ACM 14 (1971), 548–560. MR 0309356, DOI 10.1145/362637.362651
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890
- Harry Pollard, The Theory of Algebraic Numbers, Carus Monograph Series, no. 9, Mathematical Association of America, Buffalo, N.Y., 1950. MR 0037319
- Robert H. Risch, The solution of the problem of integration in finite terms, Bull. Amer. Math. Soc. 76 (1970), 605–608. MR 269635, DOI 10.1090/S0002-9904-1970-12454-5 B. L. VAN DER WAERDEN, Modern Algebra. Vol. 1, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR 10, 587.
- David R. Musser, Multivariate polynomial factorization, J. Assoc. Comput. Mach. 22 (1975), 291–308. MR 396470, DOI 10.1145/321879.321890 P. WEINBERGER, "Factoring polynomials over algebraic number fields," Trans. Mathematical Software. (To appear.)
- Hans Zassenhaus, On Hensel factorization. I, J. Number Theory 1 (1969), 291–311. MR 242793, DOI 10.1016/0022-314X(69)90047-X MACSYMA Reference Manual, The MATHLAB group, Project MAC, M.I.T., Cambridge, Mass., September 1974.
Additional Information
- © Copyright 1976 American Mathematical Society
- Journal: Math. Comp. 30 (1976), 324-336
- MSC: Primary 12-04
- DOI: https://doi.org/10.1090/S0025-5718-1976-0568283-X
- MathSciNet review: 0568283