Overlap-free Karatsuba-Ofman polynomial multiplication algorithms

被引：57

作者：

Fan, H. ^{[1
]}

Sun, J.

Gu, M.

Lam, K. -Y.

机构：

[1] Tsinghua Univ, Key Lab Informat Syst Secur, Beijing 100084, Peoples R China

来源：

IET INFORMATION SECURITY | 2010年 / 4卷 / 01期

关键词：

PARALLEL MULTIPLIERS; COMPLEXITY; ARCHITECTURE; GF(2(M)); 5-TERM; 6-TERM;

D O I：

10.1049/iet-ifs.2009.0039

中图分类号：

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

学科分类号：

0812 ;

摘要：

The authors describe how a simple way to split input operands allows for fast VLSI implementations of subquadratic GF(2)[x] Karatsuba-Ofman multipliers. The theoretical XOR gate delay of the resulting multipliers is reduced significantly. For example, it is reduced by about 33 and 25% for n = 2(t) and n 3(t) (t > 1), respectively. To the best of our knowledge, this parameter has never been improved since the original Karatsuba-Ofman algorithm was first used to design GF(2(n)) multipliers in 1990.

引用

页码：8 / 14

页数：7

共 35 条

[1]

Afanasyev V. B., 1990, P 2 INT WORKSH ALG C, P6

[2]

[Anonymous], 1980, ARITHMETIC COMPLEXIT

[3]

[Anonymous], P 23 BIENN S COMM

[4] Parallel montgomery multiplication in GF(2k) using trinomial residue arithmetic [J].

Bajard, JC ;

Imbert, L ;

Jullien, GA .

17TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2005, :164-171

[5] Low complexity bit-parallel multiplier for GF(2m) defined by all-one polynomials using redundant representation [J].

Chang, KY ;

Hong, DW ;

Cho, HS .

IEEE TRANSACTIONS ON COMPUTERS, 2005, 54 (12) :1628-1630

[6]

Chang NS, 2005, LECT NOTES COMPUT SC, V3650, P288

[7] Area efficient hardware implementation of elliptic curve cryptography by iteratively applying Karatsuba's method [J].

Dyka, Z ;

Langendoerfer, P .

DESIGNERS' FORUM: DESIGN, AUTOMATION AND TEST IN EUROPE CONFERENCE AND EXHIBITION, 2005, :70-75

[8] Low complexity bit-parallel multipliers for GF(2m) with generator polynomial xm+xk+1 [J].

Elia, M ;

Leone, M ;

Visentin, C .

ELECTRONICS LETTERS, 1999, 35 (07) :551-552

[9] Polynomial basis multiplication over GF(2m) [J].

Erdem, Serdar S. ;

Yamk, Tugrul ;

Koc, Cetin K. .

ACTA APPLICANDAE MATHEMATICAE, 2006, 93 (1-3) :33-55

[10] A less recursive variant of Karatsuba-Ofman algorithm for multiplying operands of size a power of two [J].

Erdem, SS ;

Koç, ÇK .

16TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 2003, :28-35

← 1 2 3 4 →