The Bruun Factorization
The basic Bruun algorithm for powers of two factorizes zN-1 recursively via the rules:
where a is a real constant with |a| ≤ 2. At the end of the recursion, for M=1, you are left with degree-2 polynomials that can then be evaluated modulo two roots (z - ωNk) for each polynomial. Thus, at each recursive stage, all of the polynomials are factorized into two parts of half the degree, each of which has at most three nonzero terms, leading to an O (N log N) algorithm for the FFT.
Moreover, since all of these polynomials have purely real coefficients (until the very last stage), they automatically exploit the special case where the inputs xn are purely real to save roughly a factor of two in computation and storage. One can also take straightforward advantage of the case of real-symmetric data for computing the discrete cosine transform (Chen and Sorensen, 1992).
Read more about this topic: Bruun's FFT Algorithm