ON COMPUTING MULTIPLICATIVE INVERSES IN GF(2M)

被引：90
作者：
BRUNNER, H
CURIGER, A
HOFSTETTER, M
机构：
[1] The Swiss Federal Institute of Technology, Integrated Systems Laboratory, Zurich, ETH-Zentrum
来源：
IEEE TRANSACTIONS ON COMPUTERS | 1993年 / 42卷 / 08期
关键词：
FINITE FIELD ARITHMETIC; GALOIS FIELD DIVISION; MULTIPLICATIVE INVERSE; VLSI IMPLEMENTATION;
D O I：
10.1109/12.238496
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
A novel implementation for computing multiplicative inverses in Galois fields GF(2m) is presented. The algorithm used is based on a modification of Euclid's algorithm for computing the greatest common divisor of two polynomials. The asymptotic complexity is linear with m both in computation time and area requirement, thus resulting in an AT-complexity of O(m2). This is a significant improvement over the best previous proposal which achieves AT-complexity of only O(m3).
引用
收藏
页码：1010 / 1015
页数：6
相关论文
共 13 条
[1]  
Agnew G. B., 1991, Journal of Cryptology, V3, P63, DOI 10.1007/BF00196789
[2]  
Araki K., 1989, Transactions of the Institute of Electronics, Information and Communication Engineers E, VE72, P1230
[3]  
Blahut R. E., 1983, THEORY PRACTICE ERRO
[4]   SYSTOLIC VLSI ARRAYS FOR POLYNOMIAL GCD COMPUTATION [J].
BRENT, RP ;
KUNG, HT .
IEEE TRANSACTIONS ON COMPUTERS, 1984, 33 (08) :731-736
[5]   NEW DIRECTIONS IN CRYPTOGRAPHY [J].
DIFFIE, W ;
HELLMAN, ME .
IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (06) :644-654
[6]   A VLSI ARCHITECTURE FOR FAST INVERSION IN GF(2M) [J].
FENG, GL .
IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (10) :1383-1386
[7]   A COMPARISON OF VLSI ARCHITECTURE OF FINITE-FIELD MULTIPLIERS USING DUAL, NORMAL, OR STANDARD BASES [J].
HSU, IS ;
TRUONG, TK ;
DEUTSCH, LJ ;
REED, IS .
IEEE TRANSACTIONS ON COMPUTERS, 1988, 37 (06) :735-739
[8]  
ITOH T, 1988, INFORM COMPUTAT, V78, P21
[9]  
Macwilliams F. J., 1977, THEORY ERROR CORRECT
[10]  
MORII M, 1990, APPLIED ALGEBRA ALGE, P354
12