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.
Type de document :
Communication dans un congrès
International Symposium on Symbolic and Algebraic Computation - ISSAC 2000, Aug 2000, St Andrews/United Kingdom, ACM, pp.1--7, 2000
Liste complète des métadonnées

https://hal.inria.fr/inria-00099116
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:51:06
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • 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, ACM, pp.1--7, 2000. 〈inria-00099116〉

Partager

Métriques

Consultations de la notice

249