Geodesic
Improvements on the Cantor-Zassenhaus factorization algorithm
Mathematica Bohemica, Tome 140 (2015) no. 3, pp. 271-290.

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

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.
DOI : 10.21136/MB.2015.144395
Classification : 12E30, 12Y05
Keywords: polynomial factorization; Cantor-Zassenhaus algorithm 
@article{10_21136_MB_2015_144395,
     author = {Elia, Michele and Schipani, Davide},
     title = {Improvements on the {Cantor-Zassenhaus} factorization algorithm},
     journal = {Mathematica Bohemica},
     pages = {271--290},
     publisher = {mathdoc},
     volume = {140},
     number = {3},
     year = {2015},
     doi = {10.21136/MB.2015.144395},
     mrnumber = {3397257},
     zbl = {06486939},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144395/}
}
TY  - JOUR
AU  - Elia, Michele
AU  - Schipani, Davide
TI  - Improvements on the Cantor-Zassenhaus factorization algorithm
JO  - Mathematica Bohemica
PY  - 2015
SP  - 271
EP  - 290
VL  - 140
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144395/
DO  - 10.21136/MB.2015.144395
LA  - en
ID  - 10_21136_MB_2015_144395
ER  - 
%0 Journal Article
%A Elia, Michele
%A Schipani, Davide
%T Improvements on the Cantor-Zassenhaus factorization algorithm
%J Mathematica Bohemica
%D 2015
%P 271-290
%V 140
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144395/
%R 10.21136/MB.2015.144395
%G en
%F 10_21136_MB_2015_144395
Elia, Michele; Schipani, Davide. Improvements on the Cantor-Zassenhaus factorization algorithm. Mathematica Bohemica, Tome 140 (2015) no. 3, pp. 271-290. doi : 10.21136/MB.2015.144395. http://geodesic.mathdoc.fr/articles/10.21136/MB.2015.144395/

Cité par Sources :