Factorization in Z[x]
John Abbott, Victor Shoup, Paul A. Zimmermann · 2000
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.