雷德快速傅立叶变换算法

如果 N 是素数，那么非零索引集n = 1，...,N–1在模为N的乘法下形成一个群。这种群的数论的一个结果是，存在一个群的生成器(有时称为本原根，可以通过穷举搜索或稍好的算法快速找到)^[7]，以及一个整数g，使得对于任何非零索引N和对于从0，...，N-2(从q到非零N形成双射)中独特的q，存在。类似地，对于任何非零索引k和对于从0，...，N-2(从q到非零N形成双射)中独特的p，存在，其中负指数表示模的乘法逆。这意味着我们可以使用这些新的指数p和q重写DFT，如下所示:

(回想一下， 和 在N中是隐式周期性的，且。因此，所有的索引和指数都按照群算法的要求取模为N。)

上面的最后一个求和精确地是长度为N–1的两个序列 和的循环卷积(q = 0，...，N–2)，两序列定义为:

1.1 计算卷积

因为N-1是复合的，所以这种卷积可以通过卷积定理和更传统的快速傅立叶变换算法直接执行。然而，如果N-1本身有很大的质因数，需要递归使用雷德算法，这可能就没有效率了。取而代之的是，人们可以精确地计算长度-(N–1)循环卷积，方法是将它填充到至少2(N–1)–1的长度，比如2的幂，然后可以在不递归应用雷德算法的情况下，将计算时间缩短至O(N log N)以内。

因此，该算法需要O(N)次加法加上O(NlogN)次卷积时间。实际上，O(N)加法通常可以通过将加法并入卷积来执行:如果卷积是由一对FFT执行的，那么 的和由加的FFT的DC(0)输出给出，可以通过在逆FFT之前将其加到卷积的DC项上而被加到所有输出上。尽管如此，这种算法本质上比附近复合尺寸的FFT需要更多的运算，并且在实践中通常需要3-10倍的时间。

如果雷德算法是通过使用大小为N–1的FFT来计算卷积，而不是通过如上所述的零填充来执行的，那么效率很大程度上取决于N和雷德算法必须递归应用的次数。最坏的情况是，如果N-1是 ，且是素数，而-1=  ， 是素数，依此类推。在这种情况下，假设素数链一直延伸到某个有界值，雷德算法的递归应用实际上需要O()时间。叫做索菲·热尔曼素数，这种序列叫做第一类坎宁安链。然而，坎宁安链的长度被观察到比增长得更慢，所以以这种方式应用的雷德算法，其时间复杂度可能不是，尽管在最坏的情况下它可能比更差。幸运的是，零填充可以保证操作的复杂性。