Factorization in Z[x]: the searching phase
Factorization in Z[x]: the searching phase
复制标题
Z[x] 中的因式分解：搜索阶段
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
P. Zimmermann
中科院分区：
文献类型：
--
作者：
J. Abbott;V. Shoup;P. Zimmermann
在本文中，我们描述了用于加速Berlekamp-Zassenhaus算法的搜索阶段的想法，该算法最广泛地用于计算Z[x]中的因子分解。我们的想法不会改变理论上的最坏情况复杂度，但它们在实践中确实有显著的影响：特别是在搜索阶段的成本完全主导算法其余部分的情况下。本文中思想的完整实现可在图书馆NTL中公开获得[16]。我们给出了一些困难的因式分解问题的实现时间。
In this paper we describe ideas used to accelerate the Searching Phase of the Berlekamp—Zassenhaus algorithm, the algorithm most widely used for computing factorizations in Z[x]. Our ideas do not alter the theoretical worst-case complexity, but they do have a significant effect in practice: especially in those cases where the cost of the Searching Phase completely dominates the rest of the algorithm. A complete implementation of the ideas in this paper is publicly available in the library NTL [16]. We give timings of this implementation on some difficult factorization problems.