Number theoretic transforms for the calculation of convolutions
J. B. O. S. Martens · IEEE Transactions on Acoustics Speech and Signal Processing · 1983
In this paper, we present new algorithms for the calculation of convolutions by means of number theoretic transforms over modulo rings. Not only are these algorithms more efficient than currently used methods, but they are also very flexible. Indeed, using special algorithms for short convolutions allows trading computational efficiency for structural simplicity.