Next: Primitive roots of unity Up: Advanced Computer Algebra: From Newton Previous: Advanced Computer Algebra: From Newton

# 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 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 n - 1 elements such that f (r) and g(r) are known for every r R. Then the values f (rg(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 n - 1 values f (rg(r). Observe that the cost of defining f g by the values f (rg(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 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 (rg(r) for r P can be done at nearly linear time cost.
Then the multiplication of f by g, represented by their coefficients, can be done in (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 (n log(n)log(log(n))).

Subsections

Next: Primitive roots of unity Up: Advanced Computer Algebra: From Newton Previous: Advanced Computer Algebra: From Newton
Marc Moreno Maza
2004-04-27