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

MR Zbl
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.
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 
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
@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},
     year = {2015},
     volume = {140},
     number = {3},
     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
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
%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

[1] Bach, E., Shallit, J.: Algorithmic Number Theory. Volume 1: Efficient Algorithms. Foundations of Computing Series MIT Press, Cambridge (1996). | MR

[2] Ben-Or, M.: Probabilistic Algorithms in Finite Fields. Proc. 22nd Annual IEEE Symp. Foundations of Computer Science (1981), 394-398.

[3] Benjamin, A. T., Scott, J. N.: Third and fourth binomial coefficients. Fibonacci Q. 49 (2011), 99-101. | MR | Zbl

[4] Berndt, B. C., Evans, R. J., Williams, K. S.: Gauss and Jacobi Sums. Canadian Mathematical Society Series of Monographs and Advanced Texts John Wiley & Sons, New York (1998). | MR | Zbl

[5] Cantor, D. G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36 (1981), 587-592. | DOI | MR | Zbl

[6] Gould, H. W.: Combinatorial Identities. Henry W. Gould, Morgantown, W.Va. (1972). | MR | Zbl

[7] Jungnickel, D.: Finite Fields: Structure and Arithmetics. Bibliographisches Institut Wissenschaftsverlag Mannheim (1993). | MR | Zbl

[8] Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and Its Applications 20 Cambridge Univ. Press, Cambridge (1996). | MR | Zbl

[9] Monico, C., Elia, M.: An additive characterization of fibers of characters on {$\Bbb F^\ast_p$}. Int. J. Algebra 4 (2010), 109-117. | MR

[10] Monico, C., Elia, M.: Note on an additive characterization of quadratic residues modulo {$p$}. J. Comb. Inf. Syst. Sci. 31 (2006), 209-215. | MR | Zbl

[11] Rabin, M. O.: Probabilistic algorithms in finite fields. SIAM J. Comput. 9 (1980), 273-280. | DOI | MR | Zbl

[12] Raymond, D.: An Additive Characterization of Quadratic Residues. Master Degree thesis Texas Tech University (2009).

[13] Schipani, D., Elia, M.: Additive decompositions induced by multiplicative characters over finite fields. Theory and Applications of Finite Fields. The 10th International Conference on Finite Fields and Their Applications, Ghent, Belgium, 2011 Contemp. Math. 579 American Mathematical Society, Providence (2012), 179-186 M. Lavrauw et al. | DOI | MR | Zbl

[14] Schipani, D., Elia, M.: Gauss sums of the cubic character over {$ GF(2^m)$}: An elementary derivation. Bull. Pol. Acad. Sci., Math. 59 (2011), 11-18. | DOI | MR | Zbl

[15] Schmidt, W. M.: Equations over Finite Fields. An Elementary Approach. Lecture Notes in Mathematics 536 Springer, Berlin (1976). | DOI | MR | Zbl

[16] Sloane, N. J. A.: The on-line encyclopedia of integer sequences. Ann. Math. Inform. 41 (2013), 219-234. | MR | Zbl

[17] Winterhof, A.: Character sums, primitive elements, and powers in finite fields. J. Number Theory 91 (2001), 153-163. | DOI | MR | Zbl

[18] Winterhof, A.: On the distribution of powers in finite fields. Finite Fields Appl. 4 (1998), 43-54. | DOI | MR | Zbl

Cité par Sources :