Factorization in Z[x]: the searching phase - Archive ouverte HAL Access content directly
Conference Papers Year : 2000

Factorization in Z[x]: the searching phase

, , (1)
1
John Abbott
  • Function : Author
Victor Shoup
  • Function : Author

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 $\ZZ[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~\cite{Shoup00}. We give timings of this implementation on some difficult factorization problems.
Not file

Dates and versions

inria-00099116 , version 1 (26-09-2006)

Identifiers

  • HAL Id : inria-00099116 , version 1

Cite

John Abbott, Victor Shoup, Paul Zimmermann. Factorization in Z[x]: the searching phase. International Symposium on Symbolic and Algebraic Computation - ISSAC 2000, Aug 2000, St Andrews/United Kingdom, pp.1--7. ⟨inria-00099116⟩
158 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More