Prime-factor FFT algorithm

Remarks

The output map is a bijection by the Chinese remainder theorem. The input map is a bijection because $n(n_1, n_2) \equiv N_2 n_1 \pmod{N_1}$ and $N_2$ is invertible modulo $N_1$, and similarly modulo $N_2$. For the formula, $\omega_N^{N_2 n_1 k} = \omega_{N_1}^{n_1 k} = \omega_{N_1}^{n_1 k_1}$ since $k \equiv k_1 \pmod{N_1}$, and in the same way $\omega_N^{N_1 n_2 k} = \omega_{N_2}^{n_2 k_2}$. Example: $N = 6 = 2 \cdot 3$; the input order $n(n_1, n_2) = (3n_1 + 2n_2) \bmod 6$ lists $0, 2, 4$ for $n_1 = 0$ and $3, 5, 1$ for $n_1 = 1$. Coprimality is necessary: for $N_1 = N_2 = 2$ the input map gives $2n_1 + 2n_2 \bmod 4$, which takes only the values $0$ and $2$. For non-coprime factors one uses the Cooley–Tukey algorithm, which pays with twiddle factors.

Going deeper

For a student

The algorithm is due to Good and to Thomas, and is often called the Good–Thomas algorithm. It is used for lengths with several coprime factors, with each small length done by a hand-optimised module, for example Winograd's. The price is the more complicated index arithmetic. A prime-power length such as $8$ or $9$ cannot be split this way, and a Cooley–Tukey or another FFT is used for such factors.