On karatsuba multiplication algorithm

被引：6

作者：

Fang, Xianjin ^{[1
]}

Li, Longshu ^{[1
]}

机构：

[1] Anhui Univ, Minist Educ, Key Lab Intelligent Comp & Signal Proc, Hefei 230039, Peoples R China

来源：

PROCEEDINGS OF THE FIRST INTERNATIONAL SYMPOSIUM ON DATA, PRIVACY, AND E-COMMERCE | 2007年

关键词：

D O I：

10.1109/ISDPE.2007.11

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：274 / 276

页数：3

共 10 条

[1] Bernstein D. J., MULTIDIGIT MULTIPLIC
[2] Brigham E.O., 1988, The Fast Fourier Transform and Its Applications
[3] Cormen T. H., 2001, Introduction to Algorithms, V2nd
[4] Karatsuba A.A., 1963, SOV PHYS DOKL, V7, P595
[5] Knuth DE, 1981, ART COMPUTER PROGRAM, V2
[6] Menezes A, 1996, Handbook of Applied Cryptography
[7] RIVEST RL, 1978, COMMUN ACM, V21, P120, DOI 10.1145/357980.358017
[8] ROSING M, 1999, IMPLEMENTING ELLIPTI
[9] FAST MULTIPLICATION OF LARGE NUMBERS
SCHONHAGE, A
STRASSEN, V
[J]. COMPUTING, 1971, 7 (3-4) : 281 - +
[10] MORE ON SQUARING AND MULTIPLYING LARGE INTEGERS
ZURAS, D
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (08) : 899 - 908

← 1 →