Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Factoring multivariate polynomials via partial differential equations

Author: Shuhong Gao
Journal: Math. Comp. 72 (2003), 801-822
MSC (2000): Primary 12Y05, 68W30; Secondary 11Y16, 12D05, 13P05
Published electronically: February 28, 2002
MathSciNet review: 1954969
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new method is presented for factorization of bivariate polynomials over any field of characteristic zero or of relatively large characteristic. It is based on a simple partial differential equation that gives a system of linear equations. As in Berlekamp's and Niederreiter's algorithms for factoring univariate polynomials, the dimension of the solution space of the linear system is equal to the number of absolutely irreducible factors of the polynomial to be factored, and any basis for the solution space gives a complete factorization by computing gcd's and by factoring univariate polynomials over the ground field. The new method finds absolute and rational factorizations simultaneously and is easy to implement for finite fields, local fields, number fields, and the complex number field. The theory of the new method allows an effective Hilbert irreducibility theorem, thus an efficient reduction of polynomials from multivariate to bivariate.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Retrieve articles in all journals with MSC (2000): 12Y05, 68W30, 11Y16, 12D05, 13P05

Additional Information

Shuhong Gao
Affiliation: Department of Mathematical Sciences, Clemson University, Clemson, South Carolina 29634-0975

Keywords: Polynomial factorization, absolute irreducibility, partial differential equations, Hilbert irreducibility theorem
Received by editor(s): July 19, 2000
Received by editor(s) in revised form: May 8, 2001
Published electronically: February 28, 2002
Additional Notes: The author was supported in part by NSF Grant DMS9970637, NSA Grant MDA904-00-1-0048 and ONR Grant N00014-00-1-0565. Part of the work was done while the author was a member at the Mathematical Sciences Research Institute in Berkeley, CA, USA
Article copyright: © Copyright 2002 American Mathematical Society