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.
Date:||Monday, June 30, 2011, 14:00-15:00|
|Place: ||Niavaran Bldg., Niavaran Square, Tehran, Iran|