The Truncated Fourier Transform for mixed radices

The standard version of the Fast Fourier Transform (FFT) is applied to problems of size n = 2^k. For this reason, FFT-based evaluation/interpolation schemes often reduce a problem of size l to a problem of size n, where n is the smallest power of two with l < n. However, this method presents "jumps" in the complexity at powers of two; and on the other hand, n − l values are computed that are actually unnecessary for the interpolation. To mitigate this problem, a truncated variant of the FFT was designed to avoid the computation of these unnecessary values. In the initial formulation, it is assumed that n is a power of two, but some use cases (for example in finite fields) may require more general values of n. This paper presents a generalization of the Truncated Fourier Transform (TFT) for arbitrary orders. This allows to benefit from the advantages of the TFT in the general case