Next: The Fast Fourier Transform Up: Fast Polynomial Multiplication based on Previous: The Discrete Fourier Transform

## Convolution of polynomials

Let n be a positive integer and R be a primitive n-th root of unity.

Definition 3   The convolution w.r.t. n of the polynomials f =  fi xi and g =  gi xi in R[x] is the polynomial

 h  =   hk xk (17)

such that for every k = 0 ... n - 1 the coefficient hk is given by

 hk  =    fi gj (18)

The polynomial h is also denoted by f *n g or simply by f * g if not ambiguous.

Remark 2   Observe that the product of f by g is

 p  =    pk xk (19)

where for every k = 0 ... 2n - 2 the coefficient pk is given by

 pk  =    fi gj (20)

We can rearrange the polynomial p as follows.

 p = (pk xk)   +   xn  (pk+n xk) = (pk  +  pk+n xn) xk
(21)

Therefore we have

 f * g   fg mod xn-1 (22)

Example 5   Let R = /5, n = 4, u R and consider the polynomials

 f  =  x3 + 1  and  g  =  2x3 + 3x2 + x + 1. (23)

Assume that we want to multiply f and g modulo x4 = u. Then we have to arrange the product fg in a form q(x4 - u) + r where r has degree less than 4. We obtain

 f g = 2 x6 + 3 x5 + x4 + 3 x3 + 3 x2 + x + 1 = (2x2 + 3x + 1)(x4 - u) + 3x3 + 3x2 + x + 1 + (2x2 + 3x + 1)u = (2x2 + 3x + 1)(x4 - u) + 3x3 + (3 + 2u)x2 + (1 + 3u)x + (1 + u)
(24)

For u = 1 we obtain

 f * g  =  3x3 + 4x + 2 (25)

Lemma 2   For f, g R[x] univariate polynomials of degree less than n we have

 DFT(f*g)  =  DFT(f )DFT(g) (26)

where the product of the vectors DFT(f ) and DFT(g) is computed componentwise.

Proof. Since f * g and f g are equivalent modulo xn - 1, there exists a polynomial q R[x] such that

 f * g  =  f g + q (xn - 1) (27)

Hence for i = 0 ... n - 1 we have

 (f * g)() = f () g() + q()(( - 1) = f () g()
(28)

by application of Lemma 1.

Remark 3   Consider the multi-point evaluation map

 E  : (29)

Its kernel is generated by xn - 1. Since E is surjective, it follows that

 R[x]/xn - 1   Rn (30)

(which is not a surprise!) and DFT realizes this isomorphism.

If R is a field, then this a special case of the Chinese Remaindering Theorem where mi = x - for i = 0 ... n - 1.

Next: The Fast Fourier Transform Up: Fast Polynomial Multiplication based on Previous: The Discrete Fourier Transform
Marc Moreno Maza
2004-04-27