A Note on Fast Cyclic Convolution,

摘要

The note presents a new algorithm for computing the cyclic convolution of two vectors over a commutative ring. The algorithm requires n((n sub 1)+1)...((n sub k)+1)/(2to the kth power) multiplications for the convolution of two n-vectors,where n=(n sub 1)...(n sub k) is a factorization of n into factors which are pairwise relatively prime. (Author)