Irreducibility of multivariate polynomials
From MaRDI portal
Publication:1083191
This paper deals with the problem of computing the degrees and multiplicities of the irreducible factors of a given multivariate polynomial. This includes the important question of testing for irreducibility. A probabilistic reduction from multivariate to bivariate polynomials is given, over an arbitrary (effectively computable) field. It uses an expected number of field operations (and certain random choices) that is polynomial in the length of a computation by which the input polynomial is presented, and the degree of the polynomial. Over algebraic number fields and over finite fields, we obtain polynomial-time probabilistic algorithms. They are based on an effective version of Hilbert's irreducibility theorem.
Recommendations
- Irreducibility of Polynomials
- Irreducibility criteria for compositions of multivariate polynomials
- An irreducibility criterion for polynomials in several variables
- Irreducible multivariate polynomials obtained from polynomials in fewer variables
- Irreducibility of integer-valued polynomials in several variables
- scientific article; zbMATH DE number 2124951
- Irreducibility results for compositions of polynomials in several variables
- Some Pólya-type irreducibility criteria for multivariate polynomials
- On the irreducibility of bivariate polynomials
- Irreducibility criteria for compositions of multivariate polynomials over arbitrary fields
Cites work
- A Fast Monte-Carlo Test for Primality
- A Generalized Class of Polynomials that are Hard to Factor
- Approximate formulas for some functions of prime numbers
- Berechnung und Programm. I
- Definability and fast quantifier elimination in algebraically closed fields
- Diophantine equations with unknown prime numbers
- Factoring multivariate integral polynomials
- Factoring multivariate polynomials over finite fields
- Factoring numbers in O(log n) arithmetic steps
- Factoring Polynomials over Algebraic Number Fields
- Factoring Polynomials Over Large Finite Fields
- Factoring polynomials with rational coefficients
- Factoring sparse multivariate polynomials
- Factorization of Multivariate Polynomials Over Finite Fields
- Fast parallel absolute irreducibility testing
- Fast Parallel Computation of Polynomials Using Few Processors
- Fast parallel matrix and GCD computations
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- Finding the number of factors of a polynomial
- scientific article; zbMATH DE number 3838204 (Why is no real title available?)
- scientific article; zbMATH DE number 3858405 (Why is no real title available?)
- scientific article; zbMATH DE number 3935166 (Why is no real title available?)
- scientific article; zbMATH DE number 3181273 (Why is no real title available?)
- scientific article; zbMATH DE number 3723860 (Why is no real title available?)
- scientific article; zbMATH DE number 3757697 (Why is no real title available?)
- scientific article; zbMATH DE number 3461412 (Why is no real title available?)
- scientific article; zbMATH DE number 3634395 (Why is no real title available?)
- scientific article; zbMATH DE number 3804835 (Why is no real title available?)
- scientific article; zbMATH DE number 3445379 (Why is no real title available?)
- scientific article; zbMATH DE number 3449757 (Why is no real title available?)
- scientific article; zbMATH DE number 3265895 (Why is no real title available?)
- scientific article; zbMATH DE number 3390942 (Why is no real title available?)
- New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
- New NP-hard and NP-complete polynomial and integer divisibility problems
- On Hensel factorization. I
- Parallel Algorithms for Algebraic Problems
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Polynomials with Rational Coefficients Which are Hard to Compute
- Probabilistic Algorithms in Finite Fields
- Restructuring of Arithmetic Expressions For Parallel Evaluation
- Systems of distinct representatives and linear algebra
- The Computational Complexity of Continued Fractions
Cited in
(56)- Parallel methods for absolute irreducibility testing
- Factoring sparse multivariate polynomials
- Fast parallel absolute irreducibility testing
- Feasible arithmetic computations: Valiant's hypothesis
- Distances from differences of roots of polynomials to the nearest integers
- Sentences over integral domains and their computational complexities
- On the irreducibility of multivariate subresultants.
- Probabilistic absolute irreducibility test for polynomials
- Bivariate factorization using a critical fiber
- The complexity of factors of multivariate polynomials
- Effective Noether irreducibility forms and applications
- Incidences between points and curves with almost two degrees of freedom
- Testing polynomials for vanishing on Cartesian products of planar point sets: collinearity testing and related problems
- Computational aspects of irreducible polynomials
- Exact bivariate polynomial factorization over \(\mathbb Q\) by approximation of roots
- Computing Frobenius maps and factoring polynomials
- Improved dense multivariate polynomial factorization algorithms
- Pseudoirreducible polynomials: probabilistic irreducibility testing
- Boolean circuits versus arithmetic circuits
- Constructing normal bases in finite fields
- Factoring multivariate polynomials represented by black boxes: a Maple + C implementation
- Irreducibility of integer-valued polynomials in several variables
- Irreducibility of a polynomial over the field of p elements with p prime.
- Bounds for the multiplicities of the irreducible factors of a multivariate polynomial
- scientific article; zbMATH DE number 5809457 (Why is no real title available?)
- A Quick and Dirty Irreducibility Test for Multivariate Polynomials over 𝔽q
- Irreducible multivariate polynomials obtained from polynomials in fewer variables. II
- Effective Hilbert irreducibility
- scientific article; zbMATH DE number 3959582 (Why is no real title available?)
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- scientific article; zbMATH DE number 1189231 (Why is no real title available?)
- Factoring Rational Polynomials over the Complex Numbers
- scientific article; zbMATH DE number 1303540 (Why is no real title available?)
- scientific article; zbMATH DE number 1309684 (Why is no real title available?)
- Extended Hilbert Irreducibility and Its Applications
- On the complexity of multivariate polynomial division
- Irreducibility of Polynomials
- scientific article; zbMATH DE number 1418483 (Why is no real title available?)
- Irreducibility testing over local fields
- Certifying irreducibility in \(\mathbb{Z}[x]\)
- A pre-test for factoring bivariate polynomials with coefficients in \(\mathbb F_2\)
- Absolute irreducibility of polynomials via Newton polytopes
- Irreducibility of Binomials
- New Sparse Multivariate Polynomial Factorization Algorithms over Integers
- Decompositions of nonlinear input-output systems to zero the output
- New absolute irreducibility testing criteria and factorization of multivariate polynomials
- Decomposition of algebras over finite fields and number fields
- A new absolute irreducibility criterion for multivariate polynomials over finite fields
- Factoring sparse polynomials fast
- Irreducibility of some orthogonal polynomials
- Algorithmic analysis of Jacobi stability for systems of second order ordinary differential equations
- Functional decomposition of polynomials: the tame case
- 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
- Counting reducible and singular bivariate polynomials
This page was built for publication: Irreducibility of multivariate polynomials
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1083191)
