Michele Elia, Dipartimento di Electronica e Telecomunicazioni, Politecnico di Torino, Corso Duca degli Abruzzi 24, IT10129, Turin, Italy, e-mail: michele.elia7@gmail.com; Davide Schipani, Mathematics Institute, University of Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland, e-mail: davide.schipani@math.uzh.ch
Abstract: 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.
Keywords: polynomial factorization; Cantor-Zassenhaus algorithm
Classification (MSC 2010): 12Y05, 12E30
Full text available as PDF.
Access to the full text of journal articles on this site is restricted to the subscribers of Myris Trade. To activate your access, please contact Myris Trade at myris@myris.cz.
