Fast Convolution and Multiplication

Algorithm 2  

mathend000#

Theorem 2   Let n mathend000# be a power of 2 mathend000# and $\omega$ $\in$ R mathend000# a primitive n mathend000#-th root of unity. Then convolution in R[x]/$\langle$xⁿ-1$\rangle$ mathend000# and multiplication in R[x] mathend000# of polynomials whose product has degree less than n mathend000# can be performed using

• 3 n log(n) mathend000# additions in R mathend000#,
• 3/2 n log(n) + n - 2 mathend000# multiplications by a power of $\omega$ mathend000#,
• n mathend000# multiplications in R mathend000#,
• n mathend000# divisions by n mathend000# (as an element of R mathend000#),

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

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

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

$$\leq$$ (41)

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