Fast parallel absolute irreducibility testing
From MaRDI portal
Publication:1080657
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
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
- Towards a complexity theory of synchronous parallel computation
- Factoring polynomials with rational coefficients
- Equations over finite fields. An elementary approach
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Fast parallel matrix and GCD computations
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item