Factorization in Z[x]: The Searching Phase

John Abbott, Victor Shoup, Paul Zimmermann

Research output: Contribution to conferencePaperpeer-review

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. We give timings of this implementation on some difficult factorization problems.

Original languageEnglish (US)
Pages1-7
Number of pages7
StatePublished - 2000
EventProceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (ISSAC 2000) - St Andrews, UK
Duration: Aug 7 2000Aug 9 2000

Other

OtherProceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (ISSAC 2000)
CitySt Andrews, UK
Period8/7/008/9/00

ASJC Scopus subject areas

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Factorization in Z[x]: The Searching Phase'. Together they form a unique fingerprint.

Cite this