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 [J].
Drolet, G .
IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (09) :938-946
[4]   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
[5]   MODULAR CONSTRUCTION OF LOW COMPLEXITY PARALLEL MULTIPLIERS FOR A CLASS OF FINITE-FIELDS GF(2(M)) [J].
HASAN, MA ;
WANG, MZ ;
BHARGAVA, VK .
IEEE TRANSACTIONS ON COMPUTERS, 1992, 41 (08) :962-971
[6]   A MODIFIED MASSEY-OMURA PARALLEL MULTIPLIER FOR A CLASS OF FINITE-FIELDS [J].
HASAN, MA ;
WANG, MZ ;
BHARGAVA, VK .
IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (10) :1278-1280
[7]   Double-basis multiplicative inversion over GF(2m) [J].
Hasan, MA .
IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (09) :960-970
[8]   TENSOR RANK IS NP-COMPLETE [J].
HASTAD, 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) [J].
ITOH, T ;
TSUJII, S .
INFORMATION AND COMPUTATION, 1989, 83 (01) :21-40
[10]   Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields [J].
Koc, CK ;
Sunar, B .
IEEE TRANSACTIONS ON COMPUTERS, 1998, 47 (03) :353-356
12