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

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