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