Factoring sparse multivariate polynomials

DOI10.1016/0022-0000(85)90044-3zbMath0599.68037OpenAlexW1976166549MaRDI QIDQ1080656

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)

Related Items

Irreducibility of multivariate polynomials, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Reduction of bivariate polynomials from convex-dense to dense, with application to factorizations, Factoring multivariate polynomials via partial differential equations, Factors of low individual degree polynomials, Feasible arithmetic computations: Valiant's hypothesis, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Unnamed Item, Interpolating polynomials from their values, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, Unnamed Item, Sparse bivariate polynomial factorization, Improved dense multivariate polynomial factorization algorithms, Computational complexity of sentences over fields, The inverse of an automorphism in polynomial time, Latin square determinants II, The numerical factorization of polynomials, An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation, Factoring Multivariate Polynomials over Large Finite Fields, Towards toric absolute factorization, Sentences over integral domains and their computational complexities

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Diophantine equations with unknown prime numbers
• Factoring multivariate polynomials over finite fields
• Irreducibility of multivariate polynomials
• Factoring polynomials with rational coefficients
• Factoring multivariate integral polynomials
• Parallel Algorithms for Algebraic Problems
• Factoring Polynomials over Algebraic Number Fields
• Hensel and Newton Methods in Valuation Rings
• Factorization of Multivariate Polynomials Over Finite Fields
• Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Multivariate Polynomial Factorization
• Fast parallel matrix and GCD computations
• Factoring Polynomials Over Large Finite Fields