×

Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. (English) Zbl 0605.12001

Summary: Consider a polynomial \(f\) with an arbitrary but fixed number of variables and with integral coefficients. We present an algorithm which reduces the problem of finding the integral factors of \(f\) in polynomial-time in the total degree of \(f\) and the coefficient lengths of \(f\) to factoring a univariate integral polynomial. Together with A. K. Lenstra’s, H. W. Lenstra’s and L. Lovász’ polynomial-time factorization algorithm for univariate integral polynomials [Math. Ann. 261, 515–534 (1982; Zbl 0488.12001)] this algorithm implies the following theorem. Factoring an integral polynomial with a fixed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree and the size of its coefficients.
Our algorithm can be generalized to factoring multivariate polynomials with coefficients in algebraic number fields and finite fields in polynomial-time. We also present a different algorithm, based on an effective version of a Hilbert irreducibility theorem, which polynomial- time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polynomials for irreducibility.

MSC:

11R09 Polynomials (irreducibility, etc.)
68W30 Symbolic computation and algebraic computation
11Y16 Number-theoretic algorithms; complexity
12-08 Computational methods for problems pertaining to field theory
12D05 Polynomials in real and complex fields: factorization
11T06 Polynomials over finite fields

Citations:

Zbl 0488.12001
PDFBibTeX XMLCite
Full Text: DOI Link