next up previous
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 $ \omega$ $ \in$ R be a primitive n-th root of unity.

Definition 3   The convolution w.r.t. n of the polynomials f = $ \Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ fi xi and g = $ \Sigma_{{{0 \, \leq \, i \, < \, n}}}^{{}}$ gi xi in R[x] is the polynomial

h  =  $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ hk xk (17)

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

hk  =  $\displaystyle \Sigma_{{{i+j \equiv k \mod{\, n}}}}^{{}}$  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  =  $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, 2n-1}}}^{{}}$  pk xk (19)

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

pk  =  $\displaystyle \Sigma_{{{i+j = k}}}^{{}}$  fi gj (20)

We can rearrange the polynomial p as follows.

p = $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ (pk xk)   +   xn $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n-1}}}^{{}}$ (pk+n xk)
  = $\displaystyle \Sigma_{{{0 \, \leq \, k \, < \, n}}}^{{}}$ (pk  +  pk+n xnxk
(21)

Therefore we have

f * g  $\displaystyle \equiv$  fg mod xn-1 (22)

Example 5   Let R = $ \mbox{${\mathbb Z}$}$/5$ \mbox{${\mathbb Z}$}$, n = 4, u $ \in$ 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 = x$\displaystyle \sp$6 + 3 x$\displaystyle \sp$5 + x$\displaystyle \sp$4 + 3 x$\displaystyle \sp$3 + 3 x$\displaystyle \sp$2 + 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 $ \in$ R[x] univariate polynomials of degree less than n we have

DFT$\scriptstyle \omega$(f*g)  =  DFT$\scriptstyle \omega$(f )DFT$\scriptstyle \omega$(g) (26)

where the product of the vectors DFT$\scriptstyle \omega$(f ) and DFT$\scriptstyle \omega$(g) is computed componentwise.

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

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

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

(f * g)($\displaystyle \omega^{{i}}_{{}}$) = f ($\displaystyle \omega^{{i}}_{{}}$g($\displaystyle \omega^{{i}}_{{}}$) + q($\displaystyle \omega^{{i}}_{{}}$)(($\displaystyle \omega^{{{i \, n}}}_{{}}$ - 1)
  = f ($\displaystyle \omega^{{i}}_{{}}$g($\displaystyle \omega^{{i}}_{{}}$)
(28)

by application of Lemma 1. $ \qedsymbol$

Remark 3   Consider the multi-point evaluation map

E$\scriptstyle \omega$  :  $\displaystyle \left\{\vphantom{ \begin{array}{rcl} R[x] & \longmapsto & R^n \\ ...
...1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array} }\right.$$\displaystyle \begin{array}{rcl} R[x] & \longmapsto & R^n \\  f & \longmapsto & (f(1), f({\omega}), f({\omega}^2), \ldots, f({\omega}^{n-1})) \end{array}$ (29)

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

R[x]/$\displaystyle \langle$xn - 1$\displaystyle \rangle$  $\displaystyle \simeq$  Rn (30)

(which is not a surprise!) and DFT$\scriptstyle \omega$ realizes this isomorphism.

If R is a field, then this a special case of the Chinese Remaindering Theorem where mi = x - $ \omega^{{i}}_{{}}$ for i = 0 ... n - 1.


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