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.