The complete analysis of a polynomial factorization algorithm over finite fields (Q2746437)

As anticipated by the title, the authors analyze completely a polynomial factorization algorithm over finite fields. The algorithm they present and analyze operates in three stages: given a random polynomial \(P\) over a finite field, they first get a squarefree polynomial \(Q\) with the same irreducible factors as \(P\), then they factorize \(Q\) into polynomials whose irreducible factors all have the same degree and, finally, they factorize these factors. The use generating functions to describe certain parameters involved and singularity analysis to obtain asymptotic values.NEWLINENEWLINENEWLINEThis paper is the complete and revised version of an extended abstract presented at the ICALP'96 Conference [\textit{P. Flajolet}, \textit{X. Gourdon} and \textit{D. Panario}, Random polynomials and polynomial factorization, Lect. Notes Comput. Sci. 1099, 232-243 (1996; Zbl 0906.11057)].