zbMATH — the first resource for mathematics

Improvements on the Cantor-Zassenhaus factorization algorithm. (English) Zbl 1363.11100
Summary: The paper presents a careful analysis of the Cantor-Zassenhaus polynomial factorization algorithm, thus obtaining tight bounds on the performances, and proposing useful improvements. In particular, a new simplified version of this algorithm is described, which entails a lower computational cost. The key point is to use linear test polynomials, which not only reduce the computational burden, but can also provide good estimates and deterministic bounds of the number of operations needed for factoring. Specifically, the number of attempts needed to factor a given polynomial, and the least degree of a polynomial such that a factor is found with at most a fixed number of attempts, are computed. Interestingly, the results obtained demonstrate the existence of some sort of duality relationship between these two problems.

11T06 Polynomials over finite fields
11Y05 Factorization
12E05 Polynomials in general fields (irreducibility, etc.)
Full Text: Link