Factorization patterns on nonlinear families of univariate polynomials over a finite field

Abstract

We estimate the number |Aλ| of elements on a nonlinear family A of monic polynomials of Fq [T ] of degree r having factorization pattern λ := 1λ1 2λ2 ...rλr . We show that |Aλ| = T (λ) qr−m + O(qr−m−1/2), where T (λ) is the proportion of elements of the symmetric group of r elements with cycle pattern λ and m is the codimension of A. We provide explicit upper bounds for the constants underlying the O-notation in terms of λ and A with “good” behavior. We also apply these results to analyze the average-case complexity of the classical factorization algorithm restricted to A, showing that it behaves as good as in the general case.