Practical polynomial factoring in polynomial time
Practical polynomial factoring in polynomial time
复制标题
多项式时间内的实用多项式因式分解
DOI：
10.1145/1993886.1993914
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Hart W
中科院分区：
文献类型：
--
作者：
Hart W
Q[x]中的因式分解在理论上以组合重构问题为主导，而除一些罕见的多项式外，性能倾向于以Hensel提升为主导。我们提出了一种算法，对这些更常见的多项式给出了实际的改进（较少的Hensel提升）。此外，由于最好的实现在实践中要比它们的复杂度界限快得多，因此，分解的复杂度差距有25年之久。我们说明，这种复杂性差距可以通过提供与当前最佳实现相媲美的实现来缩小，并且可以证明竞争复杂性的结果。
State of the art factoring in Q[x] is dominated in theory by a combinatorial reconstruction problem while, excluding some rare polynomials, performance tends to be dominated by Hensel lifting. We present an algorithm which gives a practical improvement (less Hensel lifting) for these more common polynomials. In addition, factoring has suffered from a 25 year complexity gap because the best implementations are much faster in practice than their complexity bounds. We illustrate that this complexity gap can be closed by providing an implementation which is comparable to the best current implementations and for which competitive complexity results can be proved.
登录
查看更多内容
数域上的相对 van Hoeij 算法
影响因子：
0.7
作者：
K. Belabas
通讯作者：
K. Belabas
Z[x] 中的因式分解：搜索阶段
DOI：
--
发表时间：
2000
期刊：
International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
J. Abbott;V. Shoup;P. Zimmermann
通讯作者：
P. Zimmermann
在有理数上分解单变量多项式
DOI：
--
发表时间：
2009
期刊：
ACCA
影响因子：
--
作者：
A. Novocin;M. V. Hoeij
通讯作者：
M. V. Hoeij
在全局域上分解多项式 I
影响因子：
0.7
作者：
M. Pohst
通讯作者：
M. Pohst
多项式因式分解锐界、高效算法
影响因子：
0.7
作者：
B. Beauzamy;V. Trevisan;Paul S. Wang
通讯作者：
Paul S. Wang