形式陈述

对长度 $n=2^k$ 的序列，DFT 为

$${\hat{a}}_j=\sum _{m=0}^{n-1}{a}_m{\omega }_n^{jm}.$$

Cooley–Tukey 分解把偶数下标与奇数下标系数分别视为两个长度 $n/2$ 的 DFT，再用旋转因子合并，得到递归 $T(n)=2T(n/2)+O(n)=O(n\log n)$。 多项式卷积经零填充、两次正变换、逐点乘法和逆变换完成。

直觉

从系数表示切换到单位根上的点值表示后，多项式乘法变成逐点乘法；递归利用单位根在平方后折半的结构。

例子与边界

零填充长度必须至少覆盖卷积结果次数。浮点 FFT 需处理舍入误差；模整数卷积可使用满足单位根条件的 NTT。DFT 定义中的正负号与归一化约定必须前后一致。

推论与应用

用于多项式乘法、卷积、信号处理、大整数乘法和许多生成函数算法。

参考资料

• James W. Cooley, John W. Tukey, An Algorithm for the Machine Calculation of Complex Fourier Series (1965), original FFT decomposition.
• Jeff Erickson, Algorithms (2019/2026 notes), FFT and polynomial multiplication.