Modular Las Vegas algorithms for polynomial absolute factorization

DOI10.1016/J.JSC.2010.06.010MaRDI QIDQ607052zbMATH OpenOpenAlexFDO

Authors Cristina Bertone, Guillaume Chèze, André Galligo

Publication date 19 November 2010

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

Full work available at URL https://arxiv.org/abs/0911.5024

zbMATH Keywords

Newton polytopeLLL algorithmabsolute factorizationmodular computations

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Polynomials, factorization in commutative rings (13P05)

Abstract: Let $$ be an irreducible polynomial over $QQ$. We give a Las Vegas absolute irreducibility test based on a property of the Newton polytope of $f$, or more precisely, of $f$ modulo some prime integer $p$. The same idea of choosing a $p$ satisfying some prescribed properties together with $LLL$ is used to provide a new strategy for absolute factorization of $f(X,Y)$. We present our approach in the bivariate case but the techniques extend to the multivariate case. Maple computations show that it is efficient and promising as we are able to factorize some polynomials of degree up to 400.

Recommendations

• Parallel methods for absolute irreducibility testing
• Lifting and recombination techniques for absolute factorization
• scientific article; zbMATH DE number 1276815
• Newton polygons of higher order in algebraic number theory
• scientific article; zbMATH DE number 3968703
• Factoring polynomials and the knapsack problem
• A relative van Hoeij algorithm over number fields
• A heuristic irreducibility test for univariate polynomials
• Bounded-degree factors of lacunary multivariate polynomials
• Polynomial factorization algorithms over number fields

Cites work

• scientific article; zbMATH DE number 4128945 (Why is no real title available?)
• scientific article; zbMATH DE number 108109 (Why is no real title available?)
• scientific article; zbMATH DE number 486633 (Why is no real title available?)
• scientific article; zbMATH DE number 1936673 (Why is no real title available?)
• scientific article; zbMATH DE number 2145002 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• A polynomial reduction algorithm
• Absolute irreducibility of polynomials via Newton polytopes
• Bounds for Hilbert's irreducibility theorem
• Complexity issues in bivariate polynomial factorization
• Effective Noether irreducibility forms and applications
• Factoring multivariate polynomials via partial differential equations
• Factoring polynomials and the knapsack problem
• Factoring polynomials over global fields
• Factoring polynomials with rational coefficients
• Fast LLL-type lattice reduction
• Fast parallel absolute irreducibility testing
• Floating-Point LLL Revisited
• Four lectures on polynomial absolute factorization
• Improved dense multivariate polynomial factorization algorithms
• Lifting and recombination techniques for absolute factorization
• Numerical factorization of multivariate complex polynomials
• On multiplication and factorization of polynomials. I: Lexicographic orderings and extreme aggregates of terms
• On the parallel Risch Algorithm (II)
• On the reduction modulo p of an absolutely irreducible polynomial f(x,y)
• Probabilistic absolute irreducibility test for polynomials
• Semi-numerical absolute factorization of polynomials with integer coefficients
• Sharp precision in Hensel lifting for bivariate polynomial factorization
• The Magma algebra system. I: The user language

Cited in

(9)

• scientific article; zbMATH DE number 2145002 (Why is no real title available?)
• Towards van der Waerden’s conjecture
• Semi-numerical absolute factorization of polynomials with integer coefficients
• Four lectures on polynomial absolute factorization
• New absolute irreducibility testing criteria and factorization of multivariate polynomials
• Parallel methods for absolute irreducibility testing
• Fast parallel absolute irreducibility testing
• Infinitely Many Knots With NonIntegral Trace
• scientific article; zbMATH DE number 2151216 (Why is no real title available?)

Describes a project that uses

Uses Software

• absfact.lib
• Maple
• Magma
• CoCoA

This page was built for publication: Modular Las Vegas algorithms for polynomial absolute factorization

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