Computing composed products of polynomials
Joel V. Brawley, Shuhong Gao, Donald Mills · Contemporary mathematics - American Mathematical Society · 1999
If f(x) and g(x) are polynomials in Fq [x] of degrees m and n respectively, then the composed sum of f and g, denoted f g, is the degree mn polynomial whose roots are all sums of roots of f with roots of g. Likewise, the composed multiplication of f and g, denoted f ffi g, is the degree mn polynomial whose roots are all products of roots of f with roots of g. In 1987, Brawley and Carlitz defined a more general notion of polynomial composition, denoted by f \\Pi g, for which f g and f ffi g are special cases. They prove that when f and g are irreducible with degrees m and n coprime, then f \\Pi g is irreducible of degree mn. This gives us a way to obtain irreducibles of relatively large degree using irreducibles of smaller degrees. In this paper, we describe several methods of computing polynomial compositions of the above form and compare their time complexities.