Computer implementation of efficient discrete-convolution algorithms (Q1842459)

Algorithms are considered that evaluate discrete cyclic convolutions by transforms in a residue number system (RNS) modulo some integer. Computation in RNS makes it possible to minimize the rounding error. This approach focuses on computation with modified addition and multiplication rules, such that the condition of ``closure'' and the condition of ``exact equality'' are satisfied. Examples of such transforms are the fast Fourier transform (FFT) and the number-theoretic transform (NTT). The paper investigates, how discrete convolutions can efficiently be implemented using a special NTT, namely the complex Mersenne pseudotransform (CMPT). The number can be applied to process real sequences of maximum length \(N = 784\). Such number-theoretic transforms were already propsed by \textit{S. C. Lee} and \textit{H. Lu} [IEEE Trans. Signal Process 39, No. 6, 1314-1321 (1991; Zbl 0744.65109)].