Block Recombination Approach for Subquadratic Space Complexity Binary Field Multiplication Based on Toeplitz Matrix-Vector Product

被引：34

作者：

Hasan, M. Anwar ^{[1
]}

Meloni, Nicolas ^{[2
]}

Namin, Ashkan Hosseinzadeh ^{[3
]}

Negre, Christophe ^{[4
]}

机构：

[1] Univ Waterloo, Dept Elect & Comp Engn, 200 Univ Ave W, Waterloo, ON N2L 3G1, Canada

[2] Univ Sud Toulon Var, IMATH, F-83957 La Garde, France

[3] AMD, Markham, ON, Canada

[4] Univ Perpignan, Equipe DALI, F-66860 Perpignan, France

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2012年 / 61卷 / 02期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Binary field; subquadratic space complexity multiplier; Toeplitz matrix; block recombination; PARALLEL MULTIPLIERS; ARCHITECTURE;

D O I：

10.1109/TC.2010.276

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we present a new method for parallel binary finite field multiplication which results in subquadratic space complexity. The method is based on decomposing the building blocks of the Fan-Hasan subquadratic Toeplitz matrix-vector multiplier. We reduce the space complexity of their architecture by recombining the building blocks. In comparison to other similar schemes available in the literature, our proposal presents a better space complexity while having the same time complexity. We also show that block recombination can be used for efficient implementation of the GHASH function of Galois Counter Mode (GCM).

引用

页码：151 / 163

页数：13

共 19 条

[1]

[Anonymous], 1980, ARITHMETIC COMPLEXIT, DOI 10.1137/1.9781611970364

[2] 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

[3]

Bernstein DJ, 2009, LECT NOTES COMPUT SC, V5677, P317, DOI 10.1007/978-3-642-03356-8_19

[4]

Cohen AE, 2004, CONF REC ASILOMAR C, P471

[5] Overlap-free Karatsuba-Ofman polynomial multiplication algorithms [J].

Fan, H. ;

Sun, J. ;

Gu, M. ;

Lam, K. -Y. .

IET INFORMATION SECURITY, 2010, 4 (01) :8-14

[6] A new approach to subquadratic space complexity parallel multipliers for extended binary fields [J].

Fan, Haining ;

Hasan, M. Anwar .

IEEE TRANSACTIONS ON COMPUTERS, 2007, 56 (02) :224-233

[7] DIVISION AND BIT-SERIAL MULTIPLICATION OVER GF(QM) [J].

HASAN, MA ;

BHARGAVA, VK .

IEE PROCEEDINGS-E COMPUTERS AND DIGITAL TECHNIQUES, 1992, 139 (03) :230-236

[8] STRUCTURE OF PARALLEL MULTIPLIERS FOR A CLASS OF FIELDS GF(2M) [J].

ITOH, T ;

TSUJII, S .

INFORMATION AND COMPUTATION, 1989, 83 (01) :21-40

[9]

Karatsuba A., 1963, Sov. Phys. Doklady, V7, P595

[10]

KOBLITZ N, 1987, MATH COMPUT, V48, P203, DOI 10.1090/S0025-5718-1987-0866109-5

← 1 2 →