一种快速Mersenne数变换算法

A Fast Algorithm for Computing Mersenne Number Transforms

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

In this paper,a fast algorithm far computing 2p-point (P is an oddprime)Meresnner numebtrans forms(MNT)is presented.Its basic formation is simpleand similar to the radix-2 FFT. The p-point MNT's algorithms needn' t besto-red and (p-1)~2 multiplications (or shifts) are converted into in-place additio-ns, so that it is realized in a general purpose computer which multiply time islonger than add. This algorithm can be extended to the implementation of thepolynomial transforms (PT) in order to compute a 2p×2p-point 2-DMNT andthe number of multiplications are reduced by PT.