Нашли опечатку? Выделите ее мышкой и нажмите Ctrl+Enter
Название: Functional decomposition of polynomials: the tame case
Автор: von zur Gathen J.
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 0(nlog^2nloglogn) arithmetic operations, and a parallel algorithm with optimal depth O(logn). 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 doea not divide r.