Kaltofen, Erich Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. (English) Zbl 0605.12001 SIAM J. Comput. 14, 469-489 (1985). 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. Cited in 3 ReviewsCited in 44 Documents 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 Keywords:polynomial factorization; polynomial-time complexity; algorithm analysis; Hensel lemma; integral polynomial; Hilbert irreducibility theorem; multivariate polynomials Citations:Zbl 0488.12001 PDFBibTeX XMLCite \textit{E. Kaltofen}, SIAM J. Comput. 14, 469--489 (1985; Zbl 0605.12001) Full Text: DOI Link