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

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

*
*

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

2008-01-07