Analysis of Rabin's irreducibility test for polynomials over finite fields (Q2772930)

To construct finite extensions of finite fields one needs irreducible polynomials. An efficient algorithm was suggested by \textit{M. O. Rabin} [SIAM J. Comput. 9, 273--280 (1980; Zbl 0461.12012)]. The following observation is the key to understanding the algorithm: let \(n=\prod p_i^{m_i}\) be the factorization of the extension degree \(n\). Then \(f\in F_q[x]\) is irreducible if and only if all \(\gcd(f,x^{q^{n/p_i}}-x)\) are trivial and \(f \mid x^{q^n}-x\). To turn this into an algorithm one checks all \(\gcd\)'s according to an ordering of the \(p_i\) unless one of them fails to be trivial.NEWLINENEWLINEFirst results on the average case complexity of Rabin's algorithm were obtained by \textit{D. Panario} and \textit{A. Viola} [Lect. Notes Comput. Sci. 1380, 1--10 (1998; Zbl 0907.11044)]. As in that paper the results are also applied to the factoring method by \textit{J. von zur Gathen} and \textit{V. Shoup} [Comput. Complexity 2, 187--224 (1992; Zbl 0778.11076)].NEWLINENEWLINEIn the present paper the authors extend these results and present more details on the proofs. For a large set of splitting types of \(n\) they manage to give an optimal ordering in which the \(n/p_i\) should be tested depending on the \(p_i\) and \(m_i\)'s (this was only conjectured in the proceedings version). They study the probabilities that a random polynomial does not pass the test with respect to \(p_i\) under the condition that it has passed all tests on \(p_j, j<i\). This consideration is detailed for \(n=p\) and \(n=p_1p_2\) as these are the most frequent cases in cryptographic applications. The main tool for this study are generating functions, a powerful tool described in more detail in \textit{P. Flajolet}, \textit{X. Gourdon} and \textit{D. Panario} [J. Algorithms 40, 37--81 (2001; Zbl 1024.11079)].