Cyclotomic Basis for Computing the Discrete Fourier Transform

This paper presents a new fast algorithm for computing an N-point discrete Fourier transform. The algorithm meets the Heideman multiplicative complexity lower bound for N = {3, 4, 6, 8, 12} and is based upon the decomposition of the elements of the transform matrix into a cyclotomic basis.