On the inherent space complexity of fast parallel multipliers for GF(2m)

被引：12

作者：

Elia, M

Leone, M

机构：

[1] Politecn Torino, Dipartimento Elettron, I-10129 Turin, Italy

[2] TILAB Telecom Italia Lab, I-10148 Turin, Italy

来源：

IEEE TRANSACTIONS ON COMPUTERS | 2002年 / 51卷 / 03期

关键词：

finite fields; parallel multiplier; optimal normal basis;

D O I：

10.1109/12.990131

中图分类号：

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

学科分类号：

0812 ;

摘要：

A lower bound to the number of AND gates used in parallel multipliers for GF((2M)) under the condition that time complexity be minimum, is determined, In particular, the exact minimum number of AND gates for Primitive Normal Bases and Optimal Normal Bases of Type 11 multipliers is evaluated, This result indirectly suggests that space complexity is essentially a quadratic function of m when time complexity is kept minimum.

引用

页码：346 / 351

页数：6

共 20 条

[1] Aho A., 1975, The Design and Analysis of Computer Algorithms
[2] Dickson LE., 1958, LINEAR GROUPS EXPOSI
[3] A new representation of elements of finite fields GF(2m) yielding small complexity arithmetic circuits
Drolet, G
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (09) : 938 - 946
[4] Low complexity bit-parallel multipliers for GF(2m) with generator polynomial xm+xk+1
Elia, M
Leone, M
Visentin, C
[J]. ELECTRONICS LETTERS, 1999, 35 (07) : 551 - 552
[5] MODULAR CONSTRUCTION OF LOW COMPLEXITY PARALLEL MULTIPLIERS FOR A CLASS OF FINITE-FIELDS GF(2(M))
HASAN, MA
WANG, MZ
BHARGAVA, VK
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (08) : 962 - 971
[6] A MODIFIED MASSEY-OMURA PARALLEL MULTIPLIER FOR A CLASS OF FINITE-FIELDS
HASAN, MA
WANG, MZ
BHARGAVA, VK
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (10) : 1278 - 1280
[7] Double-basis multiplicative inversion over GF(2m)
Hasan, MA
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (09) : 960 - 970
[8] TENSOR RANK IS NP-COMPLETE
HASTAD, J
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1990, 11 (04): : 644 - 654
[9] STRUCTURE OF PARALLEL MULTIPLIERS FOR A CLASS OF FIELDS GF(2M)
ITOH, T
TSUJII, S
[J]. INFORMATION AND COMPUTATION, 1989, 83 (01) : 21 - 40
[10] Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields
Koc, CK
Sunar, B
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (03) : 353 - 356

← 1 2 →