Fast Convolution and Multiplication

Algorithm 2  

Theorem 2   Let n be a power of 2 and $\omega$ $\in$ R a primitive n-th root of unity. Then convolution in R[x]/$\langle$xⁿ-1$\rangle$ 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 $\omega$,
• n multiplications in R,
• n divisions by n (as an element of R),

leading to 9/2 n log(n) + $\cal {O}$(n) operations in R.

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

$$\leq$$ (41)

Then we have decreased the cost of about $\cal {O}$(n²) of the classical algorithm to $\cal {O}$(n log(n)).