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^n - 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$ .

Figure: FFT-based univariate polynomial multiplication over ${\mbox{${\mathbb Z}$}}/p{\mbox{${\mathbb Z}$}}$

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

$$2^{k-1} \, < \, 2 \, n \, \leq 2^k$$ (41)

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