Fast Polynomial Multiplication based on the Discrete Fourier Transform

In the whole section we consider a commutative ring $R$ with units. Let us consider two univariate polynomials $f,g \in R[x]$ of degree less than $n$ . Then their product has degree less than $2n - 1$ . Assume that we are given a finite subset $P$ of $R$ with $2 \, n - 1$ elements such that $f(r)$ and $g(r)$ are known for every $r \in R$ . Then the values $f(r) \, g(r)$ define the polynomial $f \, g$ completely. Indeed, by Lagrange interpolation we construct the polynomial $f \, g$ (which has at most $2n - 1$ coefficients) from the $2 \, n - 1$ values $f(r) \, g(r)$ . Observe that the cost of defining $f \, g$ by the values $f(r) \, g(r)$ is $2 \, n - 1$ , which is cheap!

However if we need information about $f \, g$ such as its leading coefficient or its number of terms we need to compute the coefficients of $f \, g$ . The cost of this construction is in ${\cal O}(n^2)$ .

The underlying idea of the fast polynomial multiplication based on the discrete Fourier transform is the following. Assume that there exists a subset $P$ of $R$ with $2 \, n - 1$ elements such that

• evaluating $f$ and $g$ at every $r \in P$ can be done at nearly linear time cost (such as ${\cal O}(n \, {\log}(n))$ ),
• interpolating $f(r) \, g(r)$ for $r \in P$ can be done at nearly linear time cost.

Then the multiplication of $f$ by $g$ , represented by their coefficients, can be done in ${\cal O}(n \, {\log}(n))$ .

Such sets $P$ do not always exist. This depends on the ring $R$ and the degrees of the polynomials $f$ and $g$ . However many finite fields possess such sets for small enough degrees of $f$ and $g$ . For the arbitrary ring $R$ , it can be shown that the multiplication of $f$ nad $g$ , represented by their coefficients, can be done in ${\cal O}(n \, {\log}(n) {\log}({\log}(n)))$ .