Abstract

The central objects of this talk are univariate polynomials over finite fields. We review a methodology from analytic combinatorics (generating functions, asymptotic enumeration) that allows the study of algorithmic properties, as well as the derivation of average-case analysis for these algorithms. This methodology can be naturally used to provide precise information on the decomposition of polynomials into its irreducible factors, similar to the classical problem of the decomposition of integers into primes. Examples of these results are provided. The shape of a random univariate polynomial over a finite field is also given. Then, we briefly show several results for random polynomials over finite fields that were not obtained using the above methodology from analytic combinatorics, and we comment on recent results on random matrices over finite fields. We finish with some open problems from actual research areas in finite fields where univariate polynomials play a central role but no techniques, similar to the ones presented in this talk, have been successfully employed yet.



Information: