POLYNOMIAL-TIME REDUCTIONS FROM MULTIVARIATE TO BI BIVARIATE AND UNIVARIATE INTEGRAL POLYNOMIAL FACTORIZATION

作     者：KALTOFEN, E 

作者机构：RENSSELAER POLYTECH INSTDEPT MATH SCITROYNY 12181 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (工业与应用数学会计算杂志)

年 卷 期：1985年第14卷第2期

页      面：469-489页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：Polynomial factorization Hilbert irreducibility theorem Algorithm Analysis Polynomial-Time Complexity Hensel Lemma 

摘      要：Consider a polynomial f with an arbitrary but xed number of variables with integral coefcients. We present an algorithm which reduces the problem of nding the irreducible factors of f in polynomial-time in the total degree of f the coefcient lengths of f to factoring a univariate integral polynomial. Together with A. Lenstra s, H. Lenstra s L. Lov asz polynomial-time factorization algorithm for univariate integral polynomials this algorithm implies the following theorem. Factoring an integral polynomial with a xed number of variables into irreducibles, except for the constant factors, can be accomplished in deterministic polynomial-time in the total degree the size of its coefcients. Our algo- rithm can be generalized to factoring multivariate polynomials with coefcients in algebraic number elds nite elds 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 polyno- mials for irreducibility.