Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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. $ ^{\ast \ast}$ Some machine examples with timing are included.


References [Enhancements On Off] (What's this?)

  • [1] E. R. BERLEKAMP, "Factoring polynomials over large finite fields," Math. Comp., v. 24, 1970, pp. 713-735. MR 43 #1948. MR 0276200 (43:1948)
  • [2] E. R. BERLEKAMP, "Factoring polynomials over finite fields," Bell System Tech. J., v. 46, 1967, pp. 1853-1859. MR 36 #2314. MR 0219231 (36:2314)
  • [3] D. E. KNUTH, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison-Wesley, Reading, Mass., 1969. MR 44 #3531. MR 0286318 (44:3531)
  • [4] M. MIGNOTTE, "An inequality about factors of polynomials," Math. Comp., v. 28, 1974, pp. 1153-1157. MR 0354624 (50:7102)
  • [5] D. A. MOON, MACLISP Reference Manual, Project MAC, M.I.T., Cambridge, Mass., April 1974.
  • [6] J. MOSES, "Symbolic integration: The stormy decade," Comm. ACM, v. 14, 1971, pp. 548-560. MR 46 #8466. MR 0309356 (46:8466)
  • [7] D. R. MUSSER, "Multivariate polynomial factorization," J. Assoc. Comput. Mach., v. 22, 1975, pp. 291-308. MR 0396470 (53:335a)
  • [8] H. POLLARD, The Theory of Algebraic Numbers, Carus Monographs Ser., no. 9, Wiley, New York, 1950. MR 12, 243. MR 0037319 (12:243g)
  • [9] R. RISCH, "The solution of the problem of integration in finite terms," Bull. Amer. Math. Soc., v. 76, 1970, pp. 605-608. MR 42 #4530. MR 0269635 (42:4530)
  • [10] B. L. VAN DER WAERDEN, Modern Algebra. Vol. 1, Springer, Berlin, 1930; English transl., Ungar, New York, 1949. MR 10, 587.
  • [11] P. S. WANG & L. P. ROTHSCHILD, "Factoring multivariate polynomials over the integers," Math. Comp., v. 29, 1975, pp. 935-950. MR 0396471 (53:335b)
  • [12] P. WEINBERGER, "Factoring polynomials over algebraic number fields," Trans. Mathematical Software. (To appear.)
  • [13] H. ZASSENHAUS, "On Hensel factorization. I," J. Number Theory, v. 1, 1969, pp. 291-311. MR 39 #4120. MR 0242793 (39:4120)
  • [14] MACSYMA Reference Manual, The MATHLAB group, Project MAC, M.I.T., Cambridge, Mass., September 1974.

Similar Articles

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

American Mathematical Society