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 language | English (US) |
|---|---|
| Pages | 1-7 |
| Number of pages | 7 |
| State | Published - 2000 |
| Event | Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (ISSAC 2000) - St Andrews, UK Duration: Aug 7 2000 → Aug 9 2000 |
Other
| Other | Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (ISSAC 2000) |
|---|---|
| City | St Andrews, UK |
| Period | 8/7/00 → 8/9/00 |
ASJC Scopus subject areas
- General Mathematics