Winograd´s algorithm applied to number-theoretic transforms

We show how to perform a number-theoretic transform (n.t.t.) using an algorithm analogous to that of S. Winograd for computing the discrete Fourier transform (d.f.t.). Using this algorithm, the range of data lengths and word lengths is much larger than that available with conventional fast n.t.t.s.