## Convolution of polynomials

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

Definition 3   The convolution w.r.t. of the polynomials and in is the polynomial

 (17)

such that for every the coefficient is given by

 (18)

The polynomial is also denoted by or simply by if not ambiguous.

Remark 2   Observe that the product of by is

 (19)

where for every the coefficient is given by

 (20)

We can rearrange the polynomial as follows.

 (21)

Therefore we have

 (22)

Example 5   Let , , and consider the polynomials

 (23)

Assume that we want to multiply and modulo . Then we have to arrange the product in a form where has degree less than . We obtain

 (24)

For we obtain

 (25)

Lemma 2   For univariate polynomials of degree less than we have

 (26)

where the product of the vectors and is computed componentwise.

Proof. Since and are equivalent modulo , there exists a polynomial such that

 (27)

Hence for we have

 (28)

since .

Remark 3   Consider the multi-point evaluation map

 (29)

Its kernel is generated by . Since is surjective, it follows that

 (30)

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

If is a field, then this a special case of the Chinese Remaindering Theorem where for .

Marc Moreno Maza
2008-01-07