Factoring sparse multivariate polynomials
From MaRDI portal
This paper presents a probabilistic reduction for factoring polynomials from multivariate to the bivariate case, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the size of sparse representations of input plus output, provided the number of irreducible factors is bounded. We thus obtain probabilistic polynomial-time factoring procedures over algebraic number fields and over finite fields. The reduction is based on an effective version of Hilbert's irreducibility theorem.
Recommendations
- Irreducibility of multivariate polynomials
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Factoring bivariate sparse (lacunary) polynomials
- Improved dense multivariate polynomial factorization algorithms
- Factoring multivariate polynomials over finite fields
Cites work
- Diophantine equations with unknown prime numbers
- Factoring multivariate integral polynomials
- Factoring multivariate polynomials over finite fields
- Factoring Polynomials over Algebraic Number Fields
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials with rational coefficients
- Factorization of Multivariate Polynomials Over Finite Fields
- Fast parallel matrix and GCD computations
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Hensel and Newton Methods in Valuation Rings
- scientific article; zbMATH DE number 3147675 (Why is no real title available?)
- scientific article; zbMATH DE number 3858405 (Why is no real title available?)
- scientific article; zbMATH DE number 3651744 (Why is no real title available?)
- scientific article; zbMATH DE number 3750146 (Why is no real title available?)
- scientific article; zbMATH DE number 3757697 (Why is no real title available?)
- scientific article; zbMATH DE number 3804835 (Why is no real title available?)
- scientific article; zbMATH DE number 3222940 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- Irreducibility of multivariate polynomials
- Multivariate Polynomial Factorization
- Parallel Algorithms for Algebraic Problems
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
Cited in
(44)- Towards toric absolute factorization
- Factoring multivariate polynomials over finite fields
- Irreducibility of multivariate polynomials
- Feasible arithmetic computations: Valiant's hypothesis
- The inverse of an automorphism in polynomial time
- Latin square determinants II
- Sentences over integral domains and their computational complexities
- Extracting sparse factors from multivariate integral polynomials
- The complexity and parallel implementation of two sparse multivariate Hensel lifting algorithms for polynomial factorization
- Improved dense multivariate polynomial factorization algorithms
- An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation
- Approximate factorization of multivariate polynomials using singular value decomposition
- On multivariate polynomial matrix factorization problems
- Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
- Factors of low individual degree polynomials
- scientific article; zbMATH DE number 3887067 (Why is no real title available?)
- Factoring Multivariate Polynomials over Large Finite Fields
- Factorization of Multivariate Polynomials Over Finite Fields
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- scientific article; zbMATH DE number 1542868 (Why is no real title available?)
- On the complexity of multivariate polynomial division
- scientific article; zbMATH DE number 3997161 (Why is no real title available?)
- Sparse bivariate polynomial factorization
- Factoring multivariate polynomials via partial differential equations
- scientific article; zbMATH DE number 799768 (Why is no real title available?)
- On some computations on sparse polynomials
- scientific article; zbMATH DE number 7471587 (Why is no real title available?)
- Factorization of bivariate sparse polynomials
- The numerical factorization of polynomials
- On the complexity of factoring bivariate supersparse (lacunary) polynomials
- Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials
- Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
- New Sparse Multivariate Polynomial Factorization Algorithms over Integers
- Linear independence, alternants, and applications
- Linear independence, alternants and applications
- NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
- Derandomizing multivariate polynomial factoring for low degree factors
- On solving sparse polynomial factorization related problems
- Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
- Factoring sparse polynomials fast
- Factoring bivariate sparse (lacunary) polynomials
- Interpolating polynomials from their values
- Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
- Computational complexity of sentences over fields
This page was built for publication: Factoring sparse multivariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1080656)
