Publication: Factorization patterns on nonlinear families of univariate polynomials over a finite field
No Thumbnail Available
Date
2020
Authors
Matera, Guillermo
Privitelli, Melina Lorena
Pérez, Mariana Valeria
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
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.
Description
Keywords
Citation
Matera, Guillermo; Pérez, Mariana Valeria; Privitelli, Melina Lorena; Factorization patterns on nonlinear families of univariate polynomials over a finite field (2019) Journal Of Algebraic Combinatorics, 51, pp. 103–153