矩形变换和数论变换

卷积的快速实现和离散傅立叶变换(discrete Fourier transform,DFT)的计算都是信号和图像处理中经常遇到的问题。在实践中,这些操作通常都是用快速傅立叶变换(fast Fourier transform,FFT)算法实现的。NTT在某些场合要优于基于FFT的系统。此外也有可能采用矩形变换,像Walsh/Hadamard或算法傅立叶变换,来得到DFT或卷积的近似。 1971年,Pollard[144]在有限群上定义了NTT。由于存在变换对: 其中N×N-1≡1,α∈ZM(ZM={0,1,2,...M-1},ZM=Z/MZ)是序列N的一个元素,也就是在有限群(ZM