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

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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11567/509319
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? ND
social impact