矩形变换和数论变换

　　卷积的快速实现和离散傅立叶变换（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^N≡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）