卷积的快速实现和离散傅立叶变换（discrete fourier transform，dft）的计算都是信号和图像处理中经常遇到的问题。在实践中，这些操作通常都是用快速傅立叶变换（fast fourier transform，fft）算法实现的。ntt在某些场合要优于基于fft的系统。此外也有可能采用矩形变换，像walsh／hadamard或算法傅立叶变换，来得到dft或卷积的近似。

　　1971年，pollard^[144]在有限群上定义了ntt。由于存在变换对：

　　其中n×n^-1≡1，α∈z_m（z_m＝{0，1，2，…m－1}，z_m=z／mz）是序列n的一个元素，也就是在有限群（z_m，×）中，对于所有k∈（1，2，…，n－1）有aⁿ≡1和α^k≠1。

　　对于给定的多元组（α，m，n），能够确保这样的变换对存在是非常重要的。很明显，α必须是n阶的模m。为了保证逆ntt（intt）的存在，其他的条件是：

　　（1）乘法的逆n^-1模m必须存在，也就是说，方程x×n≡1modm必须有一个解x∈z_m。

　　（2）变换矩阵|a|=|[α^kn]|的行列式必须是非零矩阵，这样矩阵才是可逆的，也就是说a^-1存在。

　　（3）如果α和m没有公共因子，或简写成gcd（α，m）=0，只能够得出乘法的逆存在。

　　（4）对于第二种情况，要用到代数学中著名的事实：ntt矩阵是vandermonde矩阵的一个特例（a［k］＝a^k_n），它满足下面的行列式：

　　如果det（v）≠0，则需要a［k］≠a［l］≠l。实际上，由于需要计算的模m，就又产生了第二个约束条件。特别是在约束条件（也就是god（πa_k-a_l，m）=1中，不能够有0因数。

　　由此得出结论，要检验ntt的存在，必须要确认：

　　对于z_p，当p为质数时，上面给出的所有条件均自动满足。在z_p中可以找到p-1阶的元素。但是变换长度p－1一般还要受到实际应用的限制，因为就“—般”乘法和模运算化简而言还是需要的，而且在二进制或qrns算法中更适合采用“标准”fft^[1145，35]。

　　在环m＝2^b中没有有价值的变换。但使用邻近的2b±1还是可能的。如果使用的是质数，则条件1和3均自动满足。接下来要讨论什么样的质数2^b±1是已知的。

　　默希尼和费尔马（mersenne和fermat）数 法国数学家马丁·默希尼（martin mersenne1588－1648）首先研究了2^b－1形式的质数，用几何级数表示为：

　　可以看出，mersenne质数的指数3也必须是质数，这是必要条件，但并不是充分条件，例如：2¹¹－1＝23×89就不是质数。最初的mersenne质数2^b－1的指数为：

　　2^b＋1类型的质数来自fermat最初的理论。fermat推测所有的2^(2t)＋1数都是质数，但是正像mersenne质数一样，这是必要条件，但不是充分条件。因为如果b是奇数，也就是b＝q2^t，则有

　　不是质数，就像（24＋1）｜（212＋1），也就是17｜4097。到目前为止己经知道了5个format质数，分别是：

　　但是欧拉（1707－1783）指出f₅＝2³²＋1可以被641除尽。到f₂₁为止还没有再出现fermat质数，这就将ntt的可能质数中的format质数减少到前5个。

　　欢迎转载，信息来源维库电子市场网（www.dzsc.com）