Fast Group-Theoretical Transform

For an arbitrary integer $n=q2^m$, where $q|2^m-1$, we find a group $G$ of order $n$ for which the $G$-spectrum of a complex signal of length $n$ can be computed in approximately $n\log_2(n/q)$ operations. In particular, for $q=2^m-1$, the number of operations is half the number of operations for FFT computation of a signal of the same length.