Factoring sparse multivariate polynomials

DOI10.1016/0022-0000(85)90044-3MaRDI QIDQ1080656zbMATH OpenOpenAlexFDO

Authors Joachim von zur Gathen, Erich L. Kaltofen

Publication date 1985

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(85)90044-3

zbMATH Keywords

finite fieldseffective version of Hilbert's irreducibility theoremprobabilistic polynomial-time factoring procedures over algebraic number fieldsprobabilistic reduction for factoring polynomials from multivariate to the bivariate case

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Polynomials in general fields (irreducibility, etc.) (12E05)

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

• 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?)
• Diophantine equations with unknown prime numbers
• Factoring Polynomials Over Large Finite Fields
• Factoring Polynomials over Algebraic Number Fields
• Factoring multivariate integral polynomials
• Factoring multivariate polynomials over finite fields
• Factoring polynomials with rational coefficients
• Factorization of Multivariate Polynomials Over Finite Fields
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Fast parallel matrix and GCD computations
• Hensel and Newton Methods in Valuation Rings
• 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)

• On the complexity of multivariate polynomial division
• On multivariate polynomial matrix factorization problems
• An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation
• Factoring sparse polynomials fast
• Deterministically factoring sparse polynomials into multilinear factors and sums of univariate polynomials
• Feasible arithmetic computations: Valiant's hypothesis
• The complexity and parallel implementation of two sparse multivariate Hensel lifting algorithms for polynomial factorization
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Factoring Multivariate Polynomials over Large Finite Fields
• scientific article; zbMATH DE number 799768 (Why is no real title available?)
• Factoring multivariate polynomials over finite fields
• Factorization of bivariate sparse polynomials
• Factoring multivariate polynomials via partial differential equations
• Factors of low individual degree polynomials
• Factoring bivariate sparse (lacunary) polynomials
• Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators
• Interpolating polynomials from their values
• Towards toric absolute factorization
• scientific article; zbMATH DE number 3997161 (Why is no real title available?)
• Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring
• New Sparse Multivariate Polynomial Factorization Algorithms over Integers
• On some computations on sparse polynomials
• scientific article; zbMATH DE number 1542868 (Why is no real title available?)
• scientific article; zbMATH DE number 3887067 (Why is no real title available?)
• Sparse bivariate polynomial factorization
• Linear independence, alternants and applications
• Factorization of Multivariate Polynomials Over Finite Fields
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Approximate factorization of multivariate polynomials using singular value decomposition
• Extracting sparse factors from multivariate integral polynomials
• Computational complexity of sentences over fields
• The inverse of an automorphism in polynomial time
• Improved dense multivariate polynomial factorization algorithms
• Linear independence, alternants, and applications
• Latin square determinants II
• On solving sparse polynomial factorization related problems
• Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations
• Sentences over integral domains and their computational complexities
• Derandomization via symmetric polytopes: poly-time factorization of certain sparse polynomials
• scientific article; zbMATH DE number 7471587 (Why is no real title available?)
• Irreducibility of multivariate polynomials
• Derandomizing multivariate polynomial factoring for low degree factors
• On the complexity of factoring bivariate supersparse (lacunary) polynomials
• The numerical factorization of polynomials

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)