基于快速傅立叶变换的大整数乘法研究  

作　　者：郭玉秀[1] 方贤进[1] 韩猛[1] 李涛[1] 

机构地区：[1]安徽理工大学计算机科学与工程学院,安徽淮南232001

出　　处：《黑龙江科技信息》2008年第19期35-35,共1页Heilongjiang Science and Technology Information

基　　金：安徽省高校自然科学基金项目项目编号:kj2007B242

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

关 键 词：大整数乘法 快速傅立叶变换 单位元的n次根 

分 类 号：O121[理学—数学] TN911.72[理学—基础数学]