Symbolic Computation Group

David R. Cheriton School of Computer Science
University of Waterloo, Waterloo, Ontario, Canada

Algorithms for Additive and Projective Polynomials
Mark Giesbrecht, University of Waterloo, Canada
Friday, October 8, 2010 at 10:15am, at U. of Western Ontario


The additive or linearized polynomials were introduced by Ore in 1933 as an analogy over finite fields to his theory of difference and difference equations over function fields. They have been employed in number theory and algebraic geometry, and applied to constructing error-correcting codes and cryptographic protocols. In this talk we will present fast algorithms for decomposing/factoring additive polynomials. We will then look at the problem of counting the number of right composition factors. This is linked (algorithmically and mathematically) to the number of rational roots of Abhyankar's projective polynomials, for which we can get explicit counts. We also develop an inverse theory, counting the number of polynomials with a given number of roots, or more generally, with a given Galois structure.

This is joint work with Joachim von zur Gathen and Konstantin Ziegler.


Last modified on Sunday, 04 November 2012, at 15:42 hours.