Factorization in Z[x]: the searching phase

John Abbott Victor Shoup Paul Zimmermann 1
1 POLKA - Polynomials, Combinatorics, Arithmetic
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
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.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00099116
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 8:51:06 AM
Last modification on : Thursday, January 11, 2018 - 6:19:48 AM

Identifiers

  • HAL Id : inria-00099116, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

284