Fast parallel absolute irreducibility testing
We present a fast parallel deterministic algorithm for testing multivariate integral polynomials for absolute irreducibility, that is irreducibility over the complex numbers. More precisely, we establish that the set of absolutely irreducible integral polynomials belongs to the complexity class NC of Boolean circuits of polynomial size and logarithmic depth. Therefore it also belongs to the class of sequentially polynomial-time problems. Our algorithm can be extended to compute in parallel one irreducible complex factor of a multivariate integral polynomial. However, the coefficients of the computed factor are only represented modulo a not necessarily irreducible polynomial specifying a splitting field. A consequence of our algorithm is that multivariate polynomials over finite fields can be tested for absolute irreducibility in deterministic sequential polynomial time in the size of the input. We also obtain a sharp bound for the last prime p for which, when taking an absolute irreducible integral polynomial modulo p, the polynomial's irreducibility closure of the finite field of order p is not preserved.
- Equations over finite fields. An elementary approach
- Factoring polynomials with rational coefficients
- Fast parallel matrix and GCD computations
- scientific article; zbMATH DE number 3834091 (Why is no real title available?)
- scientific article; zbMATH DE number 3880854 (Why is no real title available?)
- scientific article; zbMATH DE number 3920595 (Why is no real title available?)
- scientific article; zbMATH DE number 3935166 (Why is no real title available?)
- scientific article; zbMATH DE number 3723860 (Why is no real title available?)
- scientific article; zbMATH DE number 3732172 (Why is no real title available?)
- scientific article; zbMATH DE number 3755863 (Why is no real title available?)
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- Polynomial-Time Reductions from Multivariate to Bi- and Univariate Integral Polynomial Factorization
- Towards a complexity theory of synchronous parallel computation
- Parallel methods for absolute irreducibility testing
- 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
- Effective Noether irreducibility forms and applications
- 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
- Fast Detection of Stable and Count Predicates in Parallel Computations
- Values of polynomials over finite fields
- Factoring Rational Polynomials over the Complex Numbers
- Control of the non-geometrically integral reductions
- Comments on \textit{Integration of algebraic functions}
- Selected Areas in Cryptography
- The computational complexity of recognizing permutation functions
- Absolute irreducibility of polynomials via Newton polytopes
- Rational solutions of Riccati-like partial differential equations
- Modular Las Vegas algorithms for polynomial absolute factorization
- On a generalization of Stickelberger's theorem
- New absolute irreducibility testing criteria and factorization of multivariate polynomials
- Counting curves and their projections
- A unified method for multivariate polynomial factorizations
- A new absolute irreducibility criterion for multivariate polynomials over finite fields
- Encounters in symbolic computation: ideas for the ages
- 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
This page was built for publication: Fast parallel absolute irreducibility testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1080657)
