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 2*n* - 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 2*n* - 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
(*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**P*can be done at*nearly linear time cost*(such as (*n*log(*n*))), - interpolating
*f*(*r*)*g*(*r*) for*r**P*can be done at*nearly linear time cost*.

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

- Primitive roots of unity
- The Discrete Fourier Transform
- Convolution of polynomials
- The Fast Fourier Transform
- Fast Convolution and Multiplication

2004-04-27