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 (Shoup 2000). We give timings of this implementation on some difficult factorization problems.
Factorization in $Z[x]$: The Searching Phase
ABBOTT, JOHN ANTHONY;
2000-01-01
Abstract
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 (Shoup 2000). We give timings of this implementation on some difficult factorization problems.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
