A polynomial reduction from multivariate to bivariate integral polynomial factorization.
Open Access
- 5 May 1982
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 261-266
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
This publication has 5 references indexed in Scilit:
- Newton's iteration and the sparse Hensel algorithm (Extended Abstract)1981
- An improved multivariate polynomial factoring algorithmMathematics of Computation, 1978
- On square-free decomposition algorithms1976
- Multivariate Polynomial FactorizationJournal of the ACM, 1975
- Untersuchungen zum Hilbertschen Irreduzibilit tssatz.Mathematische Zeitschrift, 1931