Irreducibility of multivariate polynomials
From MaRDI portal
Publication:1083191
DOI10.1016/0022-0000(85)90043-1zbMath0604.68043MaRDI QIDQ1083191
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)90043-1
finite fields; algebraic number fields; multivariate polynomial; multiplicities; degrees; irreducible factors; effective version of Hilbert's irreducibility theorem; polynomial-time probabilistic algorithms; probabilistic reduction from multivariate to bivariate polynomials
68Q25: Analysis of algorithms and problem complexity
68W30: Symbolic computation and algebraic computation
12E05: Polynomials in general fields (irreducibility, etc.)
Related Items
Absolute irreducibility of polynomials via Newton polytopes, Decomposition of algebras over finite fields and number fields, 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, Factoring sparse multivariate polynomials, 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, Computing Frobenius maps and factoring polynomials, Improved dense multivariate polynomial factorization algorithms, Boolean circuits versus arithmetic circuits, Constructing normal bases in finite fields
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Definability and fast quantifier elimination in algebraically closed fields
- Diophantine equations with unknown prime numbers
- New NP-hard and NP-complete polynomial and integer divisibility problems
- Factoring multivariate polynomials over finite fields
- Factoring sparse multivariate polynomials
- Fast parallel absolute irreducibility testing
- Factoring polynomials with rational coefficients
- Factoring numbers in O(log n) arithmetic steps
- Factoring multivariate integral polynomials
- On Hensel factorization. I
- Berechnung und Programm. I
- Approximate formulas for some functions of prime numbers
- Fast Parallel Computation of Polynomials Using Few Processors
- Parallel Algorithms for Algebraic Problems
- A Generalized Class of Polynomials that are Hard to Factor
- Finding the number of factors of a polynomial
- The Computational Complexity of Continued Fractions
- Factoring Polynomials over Algebraic Number Fields
- 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
- Probabilistic Algorithms in Finite Fields
- New Algorithms and Lower Bounds for the Parallel Evaluation of Certain Rational Expressions and Recurrences
- Restructuring of Arithmetic Expressions For Parallel Evaluation
- A Fast Monte-Carlo Test for Primality
- Fast parallel matrix and GCD computations
- Polynomials with Rational Coefficients Which are Hard to Compute
- Systems of distinct representatives and linear algebra
- Factoring Polynomials Over Large Finite Fields