Daniel Panario, University of Toronto

Counting polynomials over finite fields and analysis of algorithms

We focus on the usage of analytic combinatorics in algebraic problems that deal with polynomials over finite fields. The kind of problems we are interested in are: factoring polynomials, testing the irreducibility of polynomials, and computing the discrete logarithm (all over finite fields). First, we briefly introduce generating functions and asymptotic analysis. Then, for each of the problems considered, we present the problem; we introduce an efficient algorithm for it; we deduce interesting parameters of the problem; and we conclude stating known results on the analysis of the algorithms.