Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
polynomial factorization; Cantor-Zassenhaus algorithm
polynomial factorization; Cantor-Zassenhaus algorithm
Summary:
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.
References:
[1] Bach, E., Shallit, J.: Algorithmic Number Theory. Volume 1: Efficient Algorithms. Foundations of Computing Series MIT Press, Cambridge (1996). MR 1406794
[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 2801795 | Zbl 1227.05030
[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 1625181 | Zbl 0906.11001
[5] Cantor, D. G., Zassenhaus, H.: A new algorithm for factoring polynomials over finite fields. Math. Comput. 36 (1981), 587-592. DOI 10.1090/S0025-5718-1981-0606517-5 | MR 0606517 | Zbl 0493.12024
[6] Gould, H. W.: Combinatorial Identities. Henry W. Gould, Morgantown, W.Va. (1972). MR 0354401 | Zbl 0263.05013
[7] Jungnickel, D.: Finite Fields: Structure and Arithmetics. Bibliographisches Institut Wissenschaftsverlag Mannheim (1993). MR 1238714 | Zbl 0779.11058
[8] Lidl, R., Niederreiter, H.: Finite Fields. Encyclopedia of Mathematics and Its Applications 20 Cambridge Univ. Press, Cambridge (1996). MR 1429394 | Zbl 0866.11069
[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 2577460
[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 2351719 | Zbl 1231.11005
[11] Rabin, M. O.: Probabilistic algorithms in finite fields. SIAM J. Comput. 9 (1980), 273-280. DOI 10.1137/0209024 | MR 0568814 | Zbl 0461.12012
[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 10.1090/conm/579/11529 | MR 2975768 | Zbl 1298.11112
[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 10.4064/ba59-1-2 | MR 2810967 | Zbl 1215.11117
[15] Schmidt, W. M.: Equations over Finite Fields. An Elementary Approach. Lecture Notes in Mathematics 536 Springer, Berlin (1976). DOI 10.1007/BFb0080437 | MR 0429733 | Zbl 0329.12001
[16] Sloane, N. J. A.: The on-line encyclopedia of integer sequences. Ann. Math. Inform. 41 (2013), 219-234. MR 3072304 | Zbl 1274.11001
[17] Winterhof, A.: Character sums, primitive elements, and powers in finite fields. J. Number Theory 91 (2001), 153-163. DOI 10.1006/jnth.2001.2675 | MR 1869323 | Zbl 1008.11069
[18] Winterhof, A.: On the distribution of powers in finite fields. Finite Fields Appl. 4 (1998), 43-54. DOI 10.1006/ffta.1997.0199 | MR 1612072 | Zbl 0910.11055
Search
Partner of
