一种快速Mersenne数变换算法

本文提出一种快速计算2p点(P为奇素数)的一维Mersenne数变换(MNT)方法.它的基本结构类似基2FFT形式,不需存贮P点MNT算法,还可以将(P-1)~2次乘法(移位)运算转变为原位的加法运算,适合于在乘法时间较长的通用计算机上实现.这种算法可以推广到多项式变换的计算中用多项式变换计算2p×2p点的二维MNT,只需较少的乘法运算.