Probabilistic absolute irreducibility test for polynomials

DOI10.1016/S0022-4049(01)00165-7MaRDI QIDQ1612137zbMATH OpenFDO

Authors Jean-François Ragot

Publication date 22 August 2002

Published in Journal of Pure and Applied Algebra (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-4049(01)00165-7

zbMATH Keywords

irreducibility testmaplemultivariate polynomials

Mathematics Subject Classification ID

Analysis of algorithms (68W40)

Review text

The paper gives a fast deterministic algorithm to do the following: given a multivariate polynomial over the integers, return ``yes if it is proven to be absolutely irreducible. It is shown that most absolutely irreducible polynomials are recognized as such by this algorithm, assuming a certain probability distribution. The algorithm is used by the computer algebra system Maple in order to avoid the more costly decision algorithm for absolute irreducibility in most cases.

Recommendations

• Fast parallel absolute irreducibility testing
• Irreducibility of multivariate polynomials
• Effective Noether irreducibility forms and applications
• A heuristic irreducibility test for univariate polynomials
• Parallel methods for absolute irreducibility testing

Cites work

• Absolute Factorization of Polynomials: A Geometric Approach
• Counting polynomials with zeros of given multiplicities in finite fields
• Effective Noether irreducibility forms and applications
• Equations over finite fields. An elementary approach
• Factoring Rational Polynomials over the Complex Numbers
• Fast parallel absolute irreducibility testing
• scientific article; zbMATH DE number 4014840 (Why is no real title available?)
• scientific article; zbMATH DE number 4128945 (Why is no real title available?)
• scientific article; zbMATH DE number 4047850 (Why is no real title available?)
• scientific article; zbMATH DE number 3723860 (Why is no real title available?)
• scientific article; zbMATH DE number 3501472 (Why is no real title available?)
• scientific article; zbMATH DE number 1253987 (Why is no real title available?)
• scientific article; zbMATH DE number 2077079 (Why is no real title available?)
• scientific article; zbMATH DE number 3893304 (Why is no real title available?)
• scientific article; zbMATH DE number 3893305 (Why is no real title available?)
• scientific article; zbMATH DE number 3233757 (Why is no real title available?)
• scientific article; zbMATH DE number 3307642 (Why is no real title available?)
• On the parallel Risch Algorithm (II)
• The Distribution of Absolutely Irreducible Polynomials in Several Indeterminates
• The distribution of irreducible polynomials in several indeterminates
• The Distribution of Irreducible Polynomials in Several Indeterminates II
• The distribution of irreducible polynomials in several indeterminates over a finite field

Cited in

(13)

• Parallel methods for absolute irreducibility testing
• Fast parallel absolute irreducibility testing
• A heuristic irreducibility test for univariate polynomials
• Effective Noether irreducibility forms and applications
• Irreducibility of random polynomials of large degree
• Lifting and recombination techniques for absolute factorization
• On the number of polynomial solutions of Bernoulli and Abel polynomial differential equations
• Pseudoirreducible polynomials: probabilistic irreducibility testing
• A note on probabilistically verifying integer and polynomial products
• scientific article; zbMATH DE number 1253987 (Why is no real title available?)
• Certifying irreducibility in \(\mathbb{Z}[x]\)
• Modular Las Vegas algorithms for polynomial absolute factorization
• Separability problems in creative telescoping

Describes a project that uses

Uses Software

• Maple

This page was built for publication: Probabilistic absolute irreducibility test for polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1612137)