Fast parallel absolute irreducibility testing

DOI10.1016/S0747-7171(85)80029-8zbMath0599.68038MaRDI QIDQ1080657

Publication date: 1985

Published in: Journal of Symbolic Computation (Search for Journal in Brave)

finite field; complexity class NC; fast parallel deterministic algorithm; sequentially polynomial-time problems; testing multivariate integral polynomials for absolute irreducibility

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

12D05: Polynomials in real and complex fields: factorization

12E05: Polynomials in general fields (irreducibility, etc.)

Related Items

Absolute irreducibility of polynomials via Newton polytopes, Rational solutions of Riccati-like partial differential equations, The computational complexity of recognizing permutation functions, Modular Las Vegas algorithms for polynomial absolute factorization, On a generalization of Stickelberger's theorem, Counting curves and their projections, A unified method for multivariate polynomial factorizations, On computing the intersection of a pair of algebraic surfaces, Computational complexity of sentences over fields, Nearly optimal algorithms for the decomposition of multivariate rational functions and the extended Lüroth theorem, Irreducibility of multivariate polynomials, Approximate factorization of multivariate polynomials and absolute irreducibility testing, Sentences over integral domains and their computational complexities, Specified precision polynomial root isolation is in NC, Irreducibility of polynomials modulo \(p\) via Newton polytopes., Probabilistic absolute irreducibility test for polynomials, Computing the irreducible real factors and components of an algebraic curve, Deterministic irreducibility testing of polynomials over large finite fields, A study of approximate polynomials. I: Representation and arithmetic, Lifting and recombination techniques for absolute factorization, Computation of Darboux polynomials and rational first integrals with bounded degree in polynomial time, Improved dense multivariate polynomial factorization algorithms, Approximate factorization of multivariate polynomials using singular value decomposition, Semi-numerical absolute factorization of polynomials with integer coefficients, Deterministic distinct-degree factorization of polynomials over finite fields, The Computational Complexity of the Resolution of Plane Curve Singularities, Values of polynomials over finite fields

Cites Work