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

Kaltofen, Erich

SIAM J. Comput. 14, 469-489 (1985).

MSC:

11R09	Polynomials (irreducibility, etc.)
68W30	Symbolic computation and algebraic computation
11Y16	Number-theoretic algorithms; complexity
12Y05	Computational aspects of field theory and polynomials (MSC2010)
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