Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization

DOI10.1137/0214035zbMath0605.12001OpenAlexW1980267752MaRDI QIDQ3743372

Erich L. Kaltofen

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/633b0b9ef66b08f18460c6ca494c1a19be4fee15

zbMATH Keywords

polynomial factorizationmultivariate polynomialsalgorithm analysisintegral polynomialpolynomial-time complexityHensel lemmaHilbert irreducibility theorem

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Number-theoretic algorithms; complexity (11Y16) Polynomials in real and complex fields: factorization (12D05) Polynomials over finite fields (11T06) Polynomials (irreducibility, etc.) (11R09) Computational methods for problems pertaining to field theory (12-08)

Related Items (44)

Factoring sparse multivariate polynomials ⋮ Fast parallel absolute irreducibility testing ⋮ Irreducibility of multivariate polynomials ⋮ Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring ⋮ Factoring multivariate polynomials via partial differential equations ⋮ Factors of low individual degree polynomials ⋮ Algorithms for near solutions to polynomial equations ⋮ Computer algebra: Past and future ⋮ Deterministic distinct-degree factorization of polynomials over finite fields ⋮ Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\) ⋮ Deformation techniques to solve generalised Pham systems ⋮ Factoring bivariate sparse (lacunary) polynomials ⋮ An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function ⋮ New Sparse Multivariate Polynomial Factorization Algorithms over Integers ⋮ Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time ⋮ A note on Gao's algorithm for polynomial factorization ⋮ Unnamed Item ⋮ On computing the intersection of a pair of algebraic surfaces ⋮ Interpolating polynomials from their values ⋮ Computation of étale cohomology on curves in single exponential time ⋮ Time-bounded termination analysis for probabilistic programs with delays ⋮ Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators ⋮ Sparse bivariate polynomial factorization ⋮ Improved dense multivariate polynomial factorization algorithms ⋮ Computing the multilinear factors of lacunary polynomials without heights ⋮ Computational complexity of sentences over fields ⋮ Random arithmetic formulas can be reconstructed efficiently ⋮ A pre-test for factoring bivariate polynomials with coefficients in \(\mathbb F_2\) ⋮ The numerical factorization of polynomials ⋮ An efficient sparse adaptation of the polytope method over \(\mathbb F_q\) and a record-high binary bivariate factorisation ⋮ Complexity of solving parametric polynomial systems ⋮ Rational solutions of Riccati-like partial differential equations ⋮ An empirical study of cache-oblivious polygon indecomposability testing ⋮ Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields ⋮ Efficient \(q\)-integer linear decomposition of multivariate polynomials ⋮ Parallel methods for absolute irreducibility testing ⋮ A conflict-driven solving procedure for poly-power constraints ⋮ Computing the irreducible real factors and components of an algebraic curve ⋮ Deterministic irreducibility testing of polynomials over large finite fields ⋮ Sentences over integral domains and their computational complexities ⋮ Computing a context-free grammar-generating series ⋮ Approximate solutions of polynomial equations. ⋮ Complexity of factoring and calculating the GCD of linear ordinary differential operators ⋮ Heuristics to sift extraneous factors in Dixon resultants

This page was built for publication: Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization