Editing Bruun's FFT algorithm (section)

== A polynomial approach to the DFT ==

Recall that the DFT is defined by the formula:
<math display="block">X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2\pi i}{N} nk }
\qquad
k = 0,\dots,N-1. </math>

For convenience, let us denote the ''N'' [[root of unity|roots of unity]] by ω<sub>''N''</sub><sup>''n''</sup> (''n''&nbsp;=&nbsp;0,&nbsp;...,&nbsp;''N''&nbsp;&minus;&nbsp;1):
<math display="block">\omega_N^n = e^{-\frac{2\pi i}{N} n }</math>
and define the polynomial ''x''(''z'') whose coefficients are ''x''<sub>''n''</sub>:
<math display="block">x(z) = \sum_{n=0}^{N-1} x_n z^n.</math>

The DFT can then be understood as a ''reduction'' of this polynomial; that is, ''X''<sub>''k''</sub> is given by:
<math display="block">X_k = x(\omega_N^k) = x(z) \mod (z - \omega_N^k)</math>
where '''mod''' denotes the [[Polynomial remainder theorem|polynomial remainder]] operation. The key to fast algorithms like Bruun's or Cooley–Tukey comes from the fact that one can perform this set of ''N'' remainder operations in recursive stages.