雷德算法

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1}$ 

若${\displaystyle N}$ 是一个质数，则${\displaystyle n=1,\ldots ,N-1}$ 之非零索引数集合即形成一整数模N乘法群。运用数论的一个结论，可知此类的群中存在一个生成元（有时亦称为原根，可由穷举搜索或其它较有效率之算法快速找到^[7]）——一个整数 ${\displaystyle g,}$ 使得对于任意的非零索引数 ${\displaystyle n\in \{1,2,\cdots ,N-1\},}$ 都存在唯一的 ${\displaystyle q\in \{0,1,\cdots ,N-2\}}$ 令 ${\displaystyle n=g^{q}{\pmod {N}}}$ ，即形成一${\displaystyle q}$ 至非零${\displaystyle n}$ 的对射；同样地，对于任意的非零索引数 ${\displaystyle k\in \{1,2,\cdots ,N-1\},}$ 都存在唯一的 ${\displaystyle p\in \{0,1,\cdots ,N-2\}}$ 令 ${\displaystyle k=g^{-p}{\pmod {N}}}$ ，其中指数的负号代表的是 ${\displaystyle g^{p}}$ 之模反元素。这代表所求之离散傅里叶变换可用新的索引数 ${\displaystyle p}$ 及 ${\displaystyle q}$ 改写如下：

${\displaystyle X_{0}=\sum _{n=0}^{N-1}x_{n},}$ 

${\displaystyle X_{g^{-p}}=x_{0}+\sum _{q=0}^{N-2}x_{g^{q}}e^{-{\frac {2\pi i}{N}}g^{-(p-q)}}\qquad p=0,\dots ,N-2}$ 

其中${\displaystyle x_{n}}$ 和${\displaystyle X_{k}}$ 皆对${\displaystyle N}$ 隐含周期性，而${\displaystyle e^{2\pi i}=1}$ 。因此，所有索引数以及指数皆可依群算术之要求取模${\displaystyle N}$ 之结果。

上式中最后的加总即为长度${\displaystyle N-1}$ （${\displaystyle q=0,\ldots ,N-2}$ ）之两数列${\displaystyle a_{q}}$ 和${\displaystyle b_{q}}$ 的循环卷积：

${\displaystyle a_{q}=x_{g^{q}}}$ 

${\displaystyle b_{q}=e^{-{\frac {2\pi i}{N}}g^{-q}}}$ 

卷积计算

由于${\displaystyle N-1}$ 必为合数，上述之循环卷积可直接由卷积定理以及其它常用之快速傅里叶变换算法求得。然而，若 ${\displaystyle N-1}$ 本身具有较大之质因数，则此作法须递回使用雷德算法，而较不具效率。替代方法之一乃是将原长度为 ${\displaystyle N-1}$ 之数列补零至长度大于${\displaystyle 2(N-1)-1}$ ，甚或是2的次方数，便可透过快速算法在${\displaystyle O(N\log {N})}$ 的时间内求得而不须递回使用雷德算法。

如此一来，此算法则需要${\displaystyle O(N)}$ 之加法运算以及${\displaystyle O(N\log {N})}$ 之卷积运算。实作上，${\displaystyle O(N)}$ 之加法常可被包含至后续的卷积运算中：若卷积是由一对快速傅里叶变换求得，则 ${\displaystyle x_{n}}$ 的加总即是 ${\displaystyle x_{0}}$ 以及 ${\displaystyle a_{q}}$ 离散傅里叶变换的第0项输出（即DC项）之和。同时，可在逆变换前先将 ${\displaystyle x_{0}}$ 加至卷积之DC项，这样可使最后的输出皆已包含${\displaystyle x_{0}}$ 。不过，此演算所需的运算步骤仍然比其它接近之合数长度的快速傅里叶变换来得多，实务上耗时是其 3 至 10 倍。

若雷德算法未使用如上的补零法，而直接透过长度${\displaystyle N-1}$ 之快速傅里叶变换计算，则其效率将取决于${\displaystyle N}$ 值以及雷德算法本身递回呼叫的次数。最坏情况乃是当${\displaystyle N-1=2N_{2}}$ 且${\displaystyle N_{2}}$ 为质数，${\displaystyle N_{2}-1=2N_{3}}$ 且${\displaystyle N_{3}}$ 为质数，依此类推；在此情况下，若上述的质数炼一直延伸至某界值，则递回雷德算法之复杂度将为${\displaystyle O(N^{2})}$ 。诸如此类的${\displaystyle N_{j}}$ 称为索菲·热尔曼质数，而它们所形成的质数数列则称为第一类康宁汉炼（英语：Cunningham chain）。然而，康宁汉炼之长度增长的速度一般而言远较${\displaystyle \log _{2}{N}}$ 慢，故如此使用雷德算法之复杂度应不为${\displaystyle O(N^{2})}$ ，但在最坏情况下复杂度仍应比${\displaystyle O(N\log {N})}$ 高。不过，使用上述的补零法，便可达到 ${\displaystyle O(N\log {N})}$ 之复杂度。