Editing Bruun's FFT algorithm (section)

===Cooley–Tukey as polynomial factorization===

The standard decimation-in-frequency (DIF) radix-''r'' Cooley–Tukey algorithm corresponds closely to a recursive factorization. For example, radix-2 DIF Cooley–Tukey factors <math>z^N-1</math> into <math>F_1 = (z^{N/2}-1)</math> and <math>F_2 = (z^{N/2}+1)</math>. These modulo operations reduce the degree of <math>x(z)</math> by 2, which corresponds to dividing the problem size by 2. Instead of recursively factorizing <math>F_2</math> directly, though, Cooley–Tukey instead first computes ''x''<sub>2</sub>(''z'' ω<sub>''N''</sub>), shifting all the roots (by a ''twiddle factor'') so that it can apply the recursive factorization of <math>F_1</math> to both subproblems. That is, Cooley–Tukey ensures that all subproblems are also DFTs, whereas this is not generally true for an arbitrary recursive factorization (such as Bruun's, below).