# Computation for composition of polynomials

Let $R$ be a ring, $f(X)$ be a polynomial with coefficients in $R$ of degree $n$. It's known that for any $\alpha \in R$, one can evaluate $f$ at $\alpha$, i.e compute $f( \alpha)$ in $O(n)$ operations in $R$ for some $k >0$ . But could we compute $f( X + \alpha )$, or more generally compute $f( \alpha X + \beta)$ in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$. Since the result is a polynomial in $X$ of degree at most $n$, I would guess there is a such way. But from the naive way, I can't just figure out a $O(n^2)$ algorithm to do this as follows: If $f(X) = \sum_{i=1}^n a_i X^i$, then one compute $g \leftarrow a_0, h \leftarrow \alpha X + \beta, g \leftarrow g+ a_{i+1} * h, h \leftarrow h* (\alpha X + \beta)$ for $0 \leq i \leq n-1$. In the $i$-th step, $g$ is a polynomial of degree $i$ and $h$ is a polynomial of degree $i+1$, so we need $O(i)$ operations in $R$ to compute $g+ a_{i+1} * h$ and $h* (\alpha X + \beta)$, so the total operations needed is $O(n^2)$.

Is there any way to do so in $O(n)$ or $O(n * ( \mathrm{log} \; n)^k )$ operations in $R$? I don't really need to know how the algorithm works, I just need an explicit reference which says this is possible.

-

The answer is yes. You can do it using Fast Fourier Transform(FFT) to make FFT you need $n \log^k n$ operations. You not really need to know what FFT do. You need only to know that you can evaluate polynomial at some $n$ points using one FFT and you can calculate the polynomial from its values at $n$ points in one FFT.
The following algorithm should work: Using FFT evaluate $F(aX+b)$ at n points it is the same as to calculate F(X) at $n$ points. Next again using FFT you can calculate $F(aX+b)$.
You might need to work in an extension of $R$ to make the FFT work (you need a primitive $n$th root of unity or so). – Emil Jeřábek May 9 '11 at 17:47