In the whole section we consider a commutative ring R with units. Let us consider two univariate polynomials f, g 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 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 (n2).
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
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 (n log(n)log(log(n))).