一种快速Mersenne数变换算法  

A Fast Algorithm for Computing Mersenne Number Transforms

作　　者：王殊[1] 

机构地区：[1]华中理工大学

出　　处：《信号处理》1989年第2期112-117,共6页Journal of Signal Processing

摘　　要：本文提出一种快速计算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.

关 键 词：MERSENNE数 MNT算法 多项式变换 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]