Improvements on the Cantor-Zassenhaus factorization algorithm

Michele Elia; Davide Schipani

Mathematica Bohemica (2015)

  • Volume: 140, Issue: 3, page 271-290
  • ISSN: 0862-7959

Abstract

top
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.

How to cite

top

Elia, Michele, and Schipani, Davide. "Improvements on the Cantor-Zassenhaus factorization algorithm." Mathematica Bohemica 140.3 (2015): 271-290. <http://eudml.org/doc/271620>.

@article{Elia2015,
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.},
author = {Elia, Michele, Schipani, Davide},
journal = {Mathematica Bohemica},
keywords = {polynomial factorization; Cantor-Zassenhaus algorithm},
language = {eng},
number = {3},
pages = {271-290},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Improvements on the Cantor-Zassenhaus factorization algorithm},
url = {http://eudml.org/doc/271620},
volume = {140},
year = {2015},
}

TY - JOUR
AU - Elia, Michele
AU - Schipani, Davide
TI - Improvements on the Cantor-Zassenhaus factorization algorithm
JO - Mathematica Bohemica
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 140
IS - 3
SP - 271
EP - 290
AB - 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.
LA - eng
KW - polynomial factorization; Cantor-Zassenhaus algorithm
UR - http://eudml.org/doc/271620
ER -

References

top
  1. Bach, E., Shallit, J., Algorithmic Number Theory. Volume 1: Efficient Algorithms, Foundations of Computing Series MIT Press, Cambridge (1996). (1996) MR1406794
  2. Ben-Or, M., Probabilistic Algorithms in Finite Fields, Proc. 22nd Annual IEEE Symp. Foundations of Computer Science (1981), 394-398. (1981) 
  3. Benjamin, A. T., Scott, J. N., Third and fourth binomial coefficients, Fibonacci Q. 49 (2011), 99-101. (2011) Zbl1227.05030MR2801795
  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). (1998) Zbl0906.11001MR1625181
  5. Cantor, D. G., Zassenhaus, H., 10.1090/S0025-5718-1981-0606517-5, Math. Comput. 36 (1981), 587-592. (1981) Zbl0493.12024MR0606517DOI10.1090/S0025-5718-1981-0606517-5
  6. Gould, H. W., Combinatorial Identities, Henry W. Gould, Morgantown, W.Va. (1972). (1972) Zbl0263.05013MR0354401
  7. Jungnickel, D., Finite Fields: Structure and Arithmetics, Bibliographisches Institut Wissenschaftsverlag Mannheim (1993). (1993) Zbl0779.11058MR1238714
  8. Lidl, R., Niederreiter, H., Finite Fields, Encyclopedia of Mathematics and Its Applications 20 Cambridge Univ. Press, Cambridge (1996). (1996) Zbl0866.11069MR1429394
  9. Monico, C., Elia, M., An additive characterization of fibers of characters on 𝔽 p * , Int. J. Algebra 4 (2010), 109-117. (2010) MR2577460
  10. Monico, C., Elia, M., Note on an additive characterization of quadratic residues modulo p , J. Comb. Inf. Syst. Sci. 31 (2006), 209-215. (2006) Zbl1231.11005MR2351719
  11. Rabin, M. O., 10.1137/0209024, SIAM J. Comput. 9 (1980), 273-280. (1980) Zbl0461.12012MR0568814DOI10.1137/0209024
  12. Raymond, D., An Additive Characterization of Quadratic Residues, Master Degree thesis Texas Tech University (2009). (2009) 
  13. Schipani, D., Elia, M., 10.1090/conm/579/11529, 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. (2012) Zbl1298.11112MR2975768DOI10.1090/conm/579/11529
  14. Schipani, D., Elia, M., 10.4064/ba59-1-2, Bull. Pol. Acad. Sci., Math. 59 (2011), 11-18. (2011) Zbl1215.11117MR2810967DOI10.4064/ba59-1-2
  15. Schmidt, W. M., 10.1007/BFb0080437, Lecture Notes in Mathematics 536 Springer, Berlin (1976). (1976) Zbl0329.12001MR0429733DOI10.1007/BFb0080437
  16. Sloane, N. J. A., The on-line encyclopedia of integer sequences, Ann. Math. Inform. 41 (2013), 219-234. (2013) Zbl1274.11001MR3072304
  17. Winterhof, A., 10.1006/jnth.2001.2675, J. Number Theory 91 (2001), 153-163. (2001) Zbl1008.11069MR1869323DOI10.1006/jnth.2001.2675
  18. Winterhof, A., 10.1006/ffta.1997.0199, Finite Fields Appl. 4 (1998), 43-54. (1998) Zbl0910.11055MR1612072DOI10.1006/ffta.1997.0199

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.