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 polynomi- als, 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 com- puted. Interestingly, the results obtained demonstrate the existence of some sort of duality relationship between these two problems.

IMPROVEMENTS ON THE CANTOR-ZASSENHAUS FACTORIZATION ALGORITHM / Elia, Michele; Davide, Schipani. - In: MATHEMATICA BOHEMICA. - ISSN 0862-7959. - STAMPA. - 140:3(2015), pp. 271-290.

IMPROVEMENTS ON THE CANTOR-ZASSENHAUS FACTORIZATION ALGORITHM

ELIA, Michele;
2015

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 polynomi- als, 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 com- puted. Interestingly, the results obtained demonstrate the existence of some sort of duality relationship between these two problems.
2015
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11583/2563342
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo