Daniel Panario: Analytic and Probabilistic Combinatorics for Polynomials over Finite Fields

Coding Theory and Cryptography Seminars

The central objects of this talk are univariate polynomials over finite fields. We survey methods and results to count polynomials satisfying certain properties, and to understand their random behaviour. 

We first comment on a methodology from analytic combinatorics that allows the study of the decomposition of polynomials into irreducible factors, the derivation of algorithmic properties, and the estimation of average-case analysis of algorithms. This methodology can be naturally used to provide precise information on the factorization 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. As an example of the methodology, periodicity properties of the iterations of random polynomials over finite fields, related to Pollard rho method, are commented. 

Then, if time allows, we briefly show several results for random polynomials over finite fields that were obtained using other methodologies based on probabilistic combinatorics. We conclude providing open problems for polynomials over finite fields related to number theory.