# Fast Polynomial Multiplication based on the Discrete Fourier Transform

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

However if we need information about such as its leading coefficient or its number of terms we need to compute the coefficients of . The cost of this construction is in .

The underlying idea of the fast polynomial multiplication based on the discrete Fourier transform is the following. Assume that there exists a subset of with elements such that

• evaluating and at every can be done at nearly linear time cost (such as ),
• interpolating for can be done at nearly linear time cost.
Then the multiplication of by , represented by their coefficients, can be done in .

Such sets do not always exist. This depends on the ring and the degrees of the polynomials and . However many finite fields possess such sets for small enough degrees of and . For the arbitrary ring , it can be shown that the multiplication of nad , represented by their coefficients, can be done in .

Subsections
Marc Moreno Maza
2008-01-07