A polynomial time algorithm for computing all minimal decompositions of a polynomial
Raoul Blankertz · ACM communications in computer algebra · 2014
The composition of two polynomials g ( h ) = g o h is a polynomial. For a given polynomial f we are interested in finding a functional decomposition f = g o h . In this paper an algorithm is described, which computes all minimal decompositions in polynomial time. In contrast to many previous decomposition algorithms this algorithm works without restrictions on the degree of the polynomial and the characteristic of the ground field. The algorithm can be iteratively applied to compute all decompositions. It is based on ideas of Landau & Miller (1985) and Zippel (1991). Additionally, an upper bound on the number of minimal decompositions is given.