Title: POLYNOMIAL-TIME REDUCTIONS FROM MULTIVARIATE TO BI- AND UNIVARIATE INTEGRAL POLYNOMIAL FACTORIZATION*
Abstract: 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 irreducible factors off in polynomial-time in the total degree off and the coefficient lengths off to factoring a univariate integi'al polynomial. Together with A. Lenstra's,.H. Lenstra's and L. Lovfisz' polynomial-time factorization algorithm for univariate integral polynomials (Math. Ann., 261 (1982), pp. 515-534) 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 ofa Hilbert IrreducibilityThebrem, which polynomial-time reduces testing multivariate polynomials for irreducibility to testing bivariate integral polynomials for irreduciblity.
Publication Year: 1985
Publication Date: 1985-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot