A Note on Fast Cyclic Convolution
Yechezkel Zalcstein · IEEE Transactions on Computers · 1971
This note presents a new algorithm for computing the cyclic convolution of two vectors over a commutative ring. The algorithm requires n(n1+1)...(nk+1)/2kmultiplications for the convolution of two n-vectors, where n=n1...nkis a factorization of n into factors which are pairwise relatively prime.