## Fast Convolution and Multiplication

Algorithm 2

Theorem 2   Let be a power of and a primitive -th root of unity. Then convolution in and multiplication in of polynomials whose product has degree less than can be performed using
• additions in ,
• multiplications by a power of ,
• multiplications in ,
• divisions by (as an element of ),
leading to operations in .

Remark 4   To multiply two arbitrary polynomials of degree less than we only need a primitive -th root of unity where

 (41)

Then we have decreased the cost of about of the classical algorithm to .

Marc Moreno Maza
2008-01-07