Abstract: Large integer multiplication is a key operation of cryptography, and its performance affects that of many cryptographic algorithms, such as RSA, ElGamal public key cryptographic algorithms. This paper tests and compares the performance 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 efficiency 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 multiplication algorithm.

Key words: large integer multiplication, Fast Fourier Transform（FFT）, divide and conquer algorithm, polynomial multiplication

摘要： 大数相乘是密码学的一种关键运算，其性能影响许多密码算法，如RSA、ElGamal等公钥密码运算的性能。对常见的大数乘法算法进行了实验、分析和比较，特别针对快速傅里叶变换（Fast Fourier Transform，FFT）算法，分析了其在大数乘法中的应用，并与其他常见大数算法的效率进行了比较，归纳了快速傅里叶变换的优势范围与劣势范围。同时，由于快速傅里叶变换计算过程中有误差，当数据位足够多时，可能导致计算结果不正确，因此进一步分析了傅里叶快速变换计算正确的数据位上限，这些工作对于快速乘法算法的正确选择有重要的实际意义。

关键词: 大数相乘, 快速傅里叶变换（FFT）, 分治法, 多项式相乘