Algorithm 2
Theorem 2
Let
be a power of
and
a primitive
th
root of unity.
Then convolution in
and
multiplication in
of polynomials whose product has degree less than
can be performed using

additions in
,

multiplications by a power of
,

multiplications in
,

divisions by
(as an element of
),
leading to
operations in
.
Figure:
FFTbased univariate polynomial multiplication over

Marc Moreno Maza
20080107