Page "Fast Fourier transform" Paragraph 14

Another polynomial viewpoint is exploited by the Winograd algorithm, which factorizes into cyclotomic polynomials — these often have coefficients of 1, 0, or − 1, and therefore require few ( if any ) multiplications, so Winograd can be used to obtain minimal-multiplication FFTs and is often used to find efficient algorithms for small factors.

Indeed, Winograd showed that the DFT can be computed with only irrational multiplications, leading to a proven achievable lower bound on the number of multiplications for power-of-two sizes ; unfortunately, this comes at the cost of many more additions, a tradeoff no longer favorable on modern processors with hardware multipliers.

In particular, Winograd also makes use of the PFA as well as an algorithm by Rader for FFTs of prime sizes.