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.
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
Titolo: | Factorization in $Z[x]$: The Searching Phase | |
Autori: | ||
Data di pubblicazione: | 2000 | |
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. | |
Handle: | http://hdl.handle.net/11567/509319 | |
ISBN: | 1581132182 | |
Appare nelle tipologie: | 04.01 - Contributo in atti di convegno |