The complexity of sparse Hensel lifting and sparse polynomial factorization

DOI10.1016/j.jsc.2019.05.001zbMath1446.13020OpenAlexW2944680259WikidataQ127906030 ScholiaQ127906030MaRDI QIDQ2284969

Baris Tuncer, Michael B. Monagan

Publication date: 15 January 2020

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

Full work available at URL: https://doi.org/10.1016/j.jsc.2019.05.001

zbMATH Keywords

polynomial factorizationsparse polynomial interpolationpolynomial Diophantine equationsmultivariate Hensel lifting

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Software, source code, etc. for problems pertaining to commutative algebra (13-04) Polynomials, factorization in commutative rings (13P05)

Related Items

A New Black Box Factorization Algorithm - the Non-monic Case, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation

Uses Software

• Maple
• POLY

Cites Work

• Interpolating polynomials from their values
• Factoring multivariate polynomials with many factors and huge coefficients
• POLY: A New Polynomial Data Structure for Maple 17
• Using Sparse Interpolation in Hensel Lifting
• Modern Computer Algebra
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• Factoring Multivariate Polynomials Over the Integers
• An Improved Multivariate Polynomial Factoring Algorithm
• Some results on counting roots of polynomials and the Sylvester resultant
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item