Convolutions of long integer sequences by means of number theoretic transforms over residue class polynomial rings
J. B. O. S. Martens, M.C. Vanwormhoudt · IEEE Transactions on Acoustics Speech and Signal Processing · 1983
In a recent paper, Dubois and Venetsanopoulos [6] have derived methods for convolving sequences of numbers belonging to a ring S, using number theoretic transforms (NTT's) over an extension ring R of S. In this paper we obtain more explicit expressions for some of their results and, more important, improve the efficiency of their methods. Attention is focused on the case R = S[z]/(P(z)), that is, R is the quotient ring of S[z], modulo the principal ideal generated by a polynomial P(z) of degree n.