计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2014年
19期
16-19
,共4页
大数相乘%快速傅里叶变换(FFT)%分治法%多项式相乘
大數相乘%快速傅裏葉變換(FFT)%分治法%多項式相乘
대수상승%쾌속부리협변환(FFT)%분치법%다항식상승
large integer multiplication%Fast Fourier Transform(FFT)%divide and conquer algorithm%polynomial multi-plication
大数相乘是密码学的一种关键运算，其性能影响许多密码算法，如RSA、ElGamal等公钥密码运算的性能。对常见的大数乘法算法进行了实验、分析和比较，特别针对快速傅里叶变换（Fast Fourier Transform，FFT）算法，分析了其在大数乘法中的应用，并与其他常见大数算法的效率进行了比较，归纳了快速傅里叶变换的优势范围与劣势范围。同时，由于快速傅里叶变换计算过程中有误差，当数据位足够多时，可能导致计算结果不正确，因此进一步分析了傅里叶快速变换计算正确的数据位上限，这些工作对于快速乘法算法的正确选择有重要的实际意义。
大數相乘是密碼學的一種關鍵運算，其性能影響許多密碼算法，如RSA、ElGamal等公鑰密碼運算的性能。對常見的大數乘法算法進行瞭實驗、分析和比較，特彆針對快速傅裏葉變換（Fast Fourier Transform，FFT）算法，分析瞭其在大數乘法中的應用，併與其他常見大數算法的效率進行瞭比較，歸納瞭快速傅裏葉變換的優勢範圍與劣勢範圍。同時，由于快速傅裏葉變換計算過程中有誤差，噹數據位足夠多時，可能導緻計算結果不正確，因此進一步分析瞭傅裏葉快速變換計算正確的數據位上限，這些工作對于快速乘法算法的正確選擇有重要的實際意義。
대수상승시밀마학적일충관건운산，기성능영향허다밀마산법，여RSA、ElGamal등공약밀마운산적성능。대상견적대수승법산법진행료실험、분석화비교，특별침대쾌속부리협변환（Fast Fourier Transform，FFT）산법，분석료기재대수승법중적응용，병여기타상견대수산법적효솔진행료비교，귀납료쾌속부리협변환적우세범위여열세범위。동시，유우쾌속부리협변환계산과정중유오차，당수거위족구다시，가능도치계산결과불정학，인차진일보분석료부리협쾌속변환계산정학적수거위상한，저사공작대우쾌속승법산법적정학선택유중요적실제의의。
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.
