Polynomial Factorization Sharp Bounds, Efficient Algorithms
Polynomial Factorization Sharp Bounds, Efficient Algorithms
复制标题
多项式因式分解锐界、高效算法
DOI：
--
复制
发表时间：
1993
影响因子：
0.7
通讯作者：
Paul S. Wang
中科院分区：
文献类型：
--
作者：
B. Beauzamy;V. Trevisan;Paul S. Wang
建立了单变量多项式在整数上因式分解的一个新的系数界。与总体界不同，新界限制了给定多项式中至少一个不可约因子的系数的大小。单因素界是由Beauzamy等人（1990）引入的加权范数推导出来的，几乎是最优的。在p进提升中有效地利用这个界可以得到一个更有效的分解算法。包括一个完整的例子和与已知系数界的比较。
A new coefficient bound is established for factoring univariate polynomials over the integers. Unlike an overall bound, the new bound limits the size of the coefficients of at least one irreducible factor of the given polynomial. The single-factor bound is derived from the weighted norm introduced in Beauzamy et al. (1990) and is almost optimal. Effective use of this bound in p-adic lifting results in a more efficient factorization algorithm. A full example and comparisons with known coefficient bounds are included.