Functional decomposition ofpolynomials: the tame case

If g and h are polynomials of degrees r and s over a field, their functional composition f=g(h) has degree n=rs. The functional decomposition problem is: given f of degree n=rs, determine whether such g and h exist, and, in the affirmative case, compute them. We first deal with univariate polynomials, and present sequential algorithms that use O(n log2n log log n) arithmetic operations, and a parallel algorithm with optimal depth O(log n). Then we consider the case where f and h are multivariate, and g is univariate. All algorithms work only in the “tame” case, where the characteristic of the field does not divide r