next up previous
Next: Computing primitive n-th roots of Up: Fast Polynomial Multiplication based on Previous: The Fast Fourier Transform

Fast Convolution and Multiplication

Algorithm 2  

\fbox{
\begin{minipage}{10 cm}
\begin{description}
\item[{\bf Input:}] $f,g \in ...
...\gamma}) \ = \ 1/n \, DTF_{{\omega}^{-1}}({\gamma})$\end{tabbing}\end{minipage}}

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$xn-1$ \rangle$ and multiplication in R[x] of polynomials whose product has degree less than n can be performed using 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 2k-th root of unity where

2k-1  <  2 n  $\displaystyle \leq$ 2k (41)

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


next up previous
Next: Computing primitive n-th roots of Up: Fast Polynomial Multiplication based on Previous: The Fast Fourier Transform
Marc Moreno Maza
2004-04-27