complete analysis of a polynomial factorization algorithm over finite fieldsJournal of Algorithms 40, 37 81 2001. doi:10.1006rjagm.2001.1158, available online at http:r rwww.idealibrary.com on The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields P. Flajolet and X. Gourdon Algorithms Project, INRIA Rocquencourt, F-78153 Le Chesnay, France E-mail: Philippe.Flajolet@inria.fr, Xavier.Gourdon@inria.fr and D. Panario School of Mathematics and Statistics, Carleton Uni¨ ersity, Ottawa K1S 5B6, Canada E-mail: daniel@math.carleton.ca Received July 7, 2000; published online June 9, 2001 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 c……