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²).

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))).