Theorem 2
Let n be a power of 2 and
R a primitive n-th
root of unity.
Then convolution in
R[x]/x^{n}-1 and
multiplication in R[x] of polynomials whose product has degree less than n
can be performed using

3 n log(n) additions in R,

3/2 n log(n) + n - 2 multiplications by a power of ,

n multiplications in R,

n divisions by n (as an element of R),

leading to
9/2 n log(n) + (n) operations in R.

Remark 4To multiply two arbitrary polynomials of degree less than
n we only need a primitive 2^{k}-th root of unity
where

2^{k-1} < 2 n 2^{k}

(41)

Then we have decreased the cost of about
(n^{2}) of the classical
algorithm to
(n log(n)).