快速傅里叶变换(FFT)是在复数域内利用单位元的n次根的特性来减少运算次数,其普遍应用到高速数字信号处理。为了实现基于FFT的时间复杂度为O(nlogn)的大整数乘法运算,阐述了在p为素数或合数时,在模p运算下,如何选取适应于快速傅里叶变换的单位元的n次原根,并且给出了单位元的n次原根满足进行DFT和逆DFT运算的一些相关证明。
科研之友
微信
新浪微博
Facebook
分享链接
