A unified treatment of parameters relevant to factoring polynomials over finite fields is given. The framework is based on generating functions for describing parameters of interest and on singularity analysis for extracting asymptotic values. An outcome is a complete analysis of the standard polynomial factorization chain that is based on the elimination of repeated factors, distinct degree factorization, and equal degree separation. Several basic statistics on polynomials over finite fields are obtained in the course of the analysis.

Additional Metadata
Persistent URL dx.doi.org/doi:10.1006/jagm.2001.1158
Journal Journal of Algorithms
Citation
Flajolet, P., Gourdon, X., & Panario, D. (2001). The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields. Journal of Algorithms, 40(1), 37–81. doi:doi:10.1006/jagm.2001.1158