A fast d.f.t. algorithm using complex integer transforms

For certain large transform lengths, Winograd´s algorithm for computing the discrete Fourier transform (d.f.t.) is extended considerably. This is accomplished by performing the cyclic convolution, required by Winograd´s method, by a fast transform over certain complex integer fields developed previously by the authors. This new algorithm requires fewer multiplications than either the standard fast Fourier transform (f.f.t.) or Winograd´s more conventional algorithm.