Title :
On Karatsuba Multiplication Algorithm
Author :
Fang, Xianjin ; Li, Longshu
Author_Institution :
Anhui Univ., Hefei
Abstract :
Algorithms in cryptosystem such as RSA and Diffie-Hellman require the large integer multiplication. This paper introduces classical Knuth multiplication, Karatsuba multiplication and their time complexity, on the basis of which a new Karatsuba trick is presented and proved to be available in theory and in practice. The experiment result reveals that the improved Karatsuba multiplication is more efficient for implementation of large integer multiplication.
Keywords :
arithmetic; computational complexity; cryptography; Diffie-Hellman; Karatsuba multiplication algorithm; RSA; classical Knuth multiplication; cryptosystem; integer multiplication; time complexity; Arithmetic; Data privacy; Elliptic curve cryptography; Fast Fourier transforms; Laboratories; Public key cryptography;
Conference_Titel :
Data, Privacy, and E-Commerce, 2007. ISDPE 2007. The First International Symposium on
Conference_Location :
Chengdu
Print_ISBN :
978-0-7695-3016-1
DOI :
10.1109/ISDPE.2007.11
