快速傅里叶变换乘法的性能研究-计算机工程与应用.PDFVIP

16 2014 ，50（19） Computer Engineering and Applications 计算机工程与应用 快速傅里叶变换乘法的性能研究 毛 庆，李顺东 MAO Qing, LI Shundong 陕西师范大学 计算机科学学院，西安 710062 School of Computer Science, Shaanxi Normal University, Xi ’an 710062, China MAO Qing, LI Shundong. Study on performance of Fast Fourier Transform multiplication. Computer Engineering and Applications, 2014, 50 （19）：16-19. Abstract ：Large integer multiplication is a key operation of cryptography, and its performance affects that of many cryp- tographic algorithms, such as RSA, ElGamal public key cryptographic algorithms. This paper tests and compares the per- formance of some frequently used large integer multiplication algorithms and focuses on the Fast Fourier Transform （FFT ）multiplication algorithm. It analyzes its advantages and the case where it is preferable and compares its time effi- ciency to other algorithms. Furthermore, when the data are large enough, it may lead to incorrect calculations because of error accumulation in FFT process. This paper further analyzes the upper limit of data bits for the FFT calculation lower than which a correct result can be obtained. This work has important practical significance for correct choosing a fast mul- tiplication algorithm. Key words ：large integer multiplication; Fast Fourier Transform （FFT ）; divide and conquer algorithm; polynomial multi- plication 摘 要：大数相乘是密码学的一种关键运算，其性能影响许多密码算法，如RSA 、ElGamal 等公钥密码运算的性能。 对常见的大数乘法算法进行了实验、分析和比较，特别针对快速傅里叶变换（Fast Fourier Transform ，FFT ）算法，分 析了其在大数乘法中的应用，并与其他常见大数算法的效率进行了比较，归纳了快速傅里叶变换的优势范围与劣势 范围。同时，由于快速傅里叶变换计算过程中有误差，当数据位足够多时，可能导致计算结果不正确，因此进一步分 析了傅里叶快速变换计算正确的数据位上限，这些工作对于快速乘法算法的正确选择有重要的实际意义。 关键词：大数相乘；快速傅里叶变换（FFT ）；分治法；多项式相乘 文献标志码：A 中图分类号：TP301.6 doi ：10.3778/j.issn. 1002-8331.1402-0018 1 引言 同的不足之处，即随着大整数数据位数的增长，算法的 大数相乘是公钥密码学的一种关键运算，其运算性 性能逐渐下降，极大影响了公钥密码算法的性能。 能