A polynomial reduction from multivariate to bivariate integral polynomial factorization.

1 January 1982

proceedings article
Published by Association for Computing Machinery (ACM)

p. 261-266
https://doi.org/10.1145/800070.802200

Abstract

Given an arbitrary but fixed integer r -&-ge; 3. We show that testing r-variate polynomials with integer coefficients for irreducibility is m-reducible in polynomial time of the total degree and the largest coefficient length to testing bivariate polynomials for irreducibility. Factoring r-variate polynomials into irreducibles is polynomial time Turing-reducible to completely factoring bivariate polynomials.

Keywords

INTEGER COEFFICIENT
FACTORING R-VARIATE POLYNOMIAL
INTEGRAL POLYNOMIAL FACTORIZATION
BIVARIATE POLYNOMIAL
R-VARIATE POLYNOMIAL
LARGEST COEFFICIENT LENGTH
POLYNOMIAL REDUCTION
POLYNOMIAL TIME
FIXED INTEGER
POLYNOMIAL TIME TURING-REDUCIBLE
TOTAL DEGREE

This publication has 0 references indexed in Scilit: