Computing the discrete Fourier transform using residue number systems in a ring of algebraic integers

A new method is described for computing anN = R^{m} = 2^{\upsilon m}-point complex discrete Fourier transform that uses quantization within a dense ring of algebraic integers in conjunction with a residue number system over this ring. The algebraic and analytic foundations for the technique are derived and discussed. The architecture for a radix-Rfast Fourier transform algorithm using a residue number system overZ[\omega], where\omegais a primitiveRth root of unity, is developed; and range and error estimates for this algorithm are derived.