Polynomial factorization: Sharp bounds, efficient algorithms

DOI10.1006/JSCO.1993.1028MaRDI QIDQ689110zbMATH OpenOpenAlexFDO

Authors Bernard Beauzamy, Vilmar Trevisan, Paul S. Wang

Publication date 16 December 1993

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

Full work available at URL https://doi.org/10.1006/jsco.1993.1028

zbMATH Keywords

\(p\)-adic liftingefficient algorithmpolynomial factorization

Mathematics Subject Classification ID

Algebraic number theory computations (11Y40) Polynomials, factorization in commutative rings (13P05) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Review text

The paper shows that, in order to realize fast algorithms, it is necessary to control the size of the coefficients in one irreducible factor. A bound on this size is presented in Theorem 1. It makes use of the weighted norm and it is almost optimal. The paper shows how to use this bound in the process of \(p\)-adic lifting in such a way to obtain an efficient algorithm. A worked example completes the paper.

Recommendations

• A fast algorithm for polynomial factorization over \(\mathbb Q_p\)
• scientific article; zbMATH DE number 1643926
• scientific article; zbMATH DE number 4069018
• scientific article; zbMATH DE number 922258
• Fast Hensel's lifting implementation using partial fraction decomposition

Cited in

(10)

• Algorithms for adaptive factorization of polynomials
• Bounds on factors in \(\mathbb Z[x]\)
• Single-factor coefficient bounds
• scientific article; zbMATH DE number 4208240 (Why is no real title available?)
• Sharp precision in Hensel lifting for bivariate polynomial factorization
• Decision making beyond arrow's “impossibility theorem,” with the analysis of effects of collusion and mutual attraction
• Each univariate complex polynomial has a ‘big’ factor
• A history of solving some famous problems in mathematical analysis
• On 7th Smale's problem
• Practical polynomial factoring in polynomial time

This page was built for publication: Polynomial factorization: Sharp bounds, efficient algorithms

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