Conversion of Multiple Cyclic Convolution System into a Single System

H. Murakami (Japan)


Cyclic convolution, DFT, Numbertheoretic transform, Multiple system.


The number theoretic transform (NTT) provides an efficient cyclic convolution algorithm for integer valued sequences. This paper introduces a multiple cyclic convolution system, which computes a set of cyclic convolutions by a single cyclic convolution by the NTT, whereby the computational efficiency is achieved. Choices of moduli numbers suitable for implementation by computers of 32 bit and 64 bit word lengths are proposed. *

Important Links:

Go Back