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

A new method is described for computing an -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- fast Fourier transform algorithm using a residue number system over , where is a primitive th root of unity, is developed; and range and error estimates for this algorithm are derived.