基于Knuth与Karatsuba乘法的大整数乘法研究  

Research on Large Integer Multiplication Based on Knuth and Karatsuba Multiplication

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

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

出　　处：《安徽理工大学学报（自然科学版）》2008年第2期67-69,共3页Journal of Anhui University of Science and Technology:Natural Science

基　　金：安徽省高校自然科学基金资助项目(KJ2007B0242)

摘　　要：在RSA、Diffie-Hellman密码系统的算法中都要用到大整数乘法算术。介绍了Knuth经典乘法、Karatsuba乘法以及它们的计算时间复杂性,在此基础上提出了一个新的大整数乘法技巧,并且在理论上和实践上被证明是有效的。实验结果也显示改进的大整数乘法算法在实现大整数乘法运算时具有更高的效率。Algorithms in cryptosystem such as RSA and Diffie-Hellman require large integer multiplica- tion. In the paper Knuth classical multiplication, Karatsuba multiplication and their time complexity were presented, on the basis of which a new large integer multiplication trick was put forward and proved available in theory and practice. The experiment showed that the improved multiplication algo-rithm is more efficient in implementation of large integer multiplication.

关 键 词：Knuth乘法 Karatsuba乘法 大整数乘法 分治法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]