Factoring multivariate polynomials over algebraic number fields

Author:
Paul S. Wang

Journal:
Math. Comp. **30** (1976), 324-336

MSC:
Primary 12-04

DOI:
https://doi.org/10.1090/S0025-5718-1976-0568283-X

Remarks:
Math. Comp. **51**, no. 184 (1988), pp. 837-839.

MathSciNet review:
0568283

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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. Some machine examples with timing are included.

**[1]**E. R. Berlekamp,*Factoring polynomials over large finite fields*, Math. Comp.**24**(1970), 713–735. MR**0276200**, https://doi.org/10.1090/S0025-5718-1970-0276200-X**[2]**E. R. Berlekamp,*Factoring polynomials over finite fields*, Bell System Tech. J.**46**(1967), 1853–1859. MR**0219231**, https://doi.org/10.1002/j.1538-7305.1967.tb03174.x**[3]**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****[4]**M. Mignotte,*An inequality about factors of polynomials*, Math. Comp.**28**(1974), 1153–1157. MR**0354624**, https://doi.org/10.1090/S0025-5718-1974-0354624-3**[5]**D. A. MOON,*MACLISP Reference Manual*, Project MAC, M.I.T., Cambridge, Mass., April 1974.**[6]**Joel Moses,*Symbolic integration: The stormy decade*, Comm. ACM**14**(1971), 548–560. MR**0309356**, https://doi.org/10.1145/362637.362651**[7]**David R. Musser,*Multivariate polynomial factorization*, J. Assoc. Comput. Mach.**22**(1975), 291–308. MR**0396470**, https://doi.org/10.1145/321879.321890**[8]**Harry Pollard,*The Theory of Algebraic Numbers*, Carus Monograph Series, no. 9, The Mathematical Association of America, Buffalo, N. Y., 1950. MR**0037319****[9]**Robert H. Risch,*The solution of the problem of integration in finite terms*, Bull. Amer. Math. Soc.**76**(1970), 605–608. MR**0269635**, https://doi.org/10.1090/S0002-9904-1970-12454-5**[10]**B. L. VAN DER WAERDEN,*Modern Algebra*. Vol. 1, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR**10**, 587.**[11]**Paul S. Wang and Linda Preiss Rothschild,*Factoring multivariate polynomials over the integers*, Math. Comput.**29**(1975), 935–950. MR**0396471**, https://doi.org/10.1090/S0025-5718-1975-0396471-3**[12]**P. WEINBERGER, "Factoring polynomials over algebraic number fields,"*Trans. Mathematical Software*. (To appear.)**[13]**Hans Zassenhaus,*On Hensel factorization. I*, J. Number Theory**1**(1969), 291–311. MR**0242793**, https://doi.org/10.1016/0022-314X(69)90047-X**[14]***MACSYMA Reference Manual*, The MATHLAB group, Project MAC, M.I.T., Cambridge, Mass., September 1974.

Retrieve articles in *Mathematics of Computation*
with MSC:
12-04

Retrieve articles in all journals with MSC: 12-04

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1976-0568283-X

Article copyright:
© Copyright 1976
American Mathematical Society