Editing Bruun's FFT algorithm (section)

=== Generalization to arbitrary radices ===

The Bruun factorization, and thus the Bruun FFT algorithm, was generalized to handle arbitrary ''even'' composite lengths, i.e. dividing the polynomial degree by an arbitrary ''radix'' (factor), as follows. First, we define a set of polynomials {{math|''φ''<sub>''N'',''α''</sub>(''z'')}} for positive integers {{mvar|N}} and for {{mvar|α}} in {{closed-open|0, 1}} by:
<math display="block">\phi_{N, \alpha}(z) = \begin{cases}
z^{2N} - 2 \cos (2 \pi \alpha) z^N + 1 & \text{if } 0 < \alpha < 1 \\ \\
z^{2N} - 1 & \text{if } \alpha = 0
\end{cases} </math>

Note that all of the polynomials that appear in the Bruun factorization above can be written in this form. The zeroes of these polynomials are <math>e^{2\pi i ( \pm\alpha + k ) / N}</math> for <math>k = 0, 1, \dots, N-1</math> in the <math>\alpha \neq 0</math> case, and <math>e^{2\pi i k / 2N}</math> for <math>k = 0, 1, \dots, 2N-1</math> in the <math>\alpha = 0</math> case. Hence these polynomials can be recursively factorized for a factor (radix) {{mvar|r}} via:

<math display="block">\phi_{rM, \alpha}(z) = \begin{cases}
\prod_{\ell=0}^{r-1} \phi_{M,(\alpha+\ell)/r} & \text{if } 0 < \alpha \leq 0.5 \\ \\
\prod_{\ell=0}^{r-1} \phi_{M,(1-\alpha+\ell)/r} & \text{if } 0.5 < \alpha < 1 \\ \\
\prod_{\ell=0}^{r-1} \phi_{M,\ell/(2r)} & \text{if } \alpha = 0
\end{cases} </math>