有限域GF (2m)上的一個(gè)新的求逆算法
A NEW ALGORITHM FOR COMPUTING INVERSES IN THE FINITE FIELD GF(2m)
-
摘要: 根據(jù)有限域GF(2m)上的正規(guī)基表示和Massey-Omura乘法器,本文提出了一個(gè)復(fù)雜性為O(logm)的求逆算法。新算法完成一次求逆運(yùn)算只需要[log2(m-1)]+w(m-1)-1次乘法和m-1次循環(huán)移位,這里[x]表示小于等于x的最大整數(shù),w(m-1)表示m-1的二進(jìn)制表示中1的個(gè)數(shù)。
-
關(guān)鍵詞:
- 信息論; 數(shù)字通信; 算法; 有限域; 正規(guī)基; 逆
Abstract: A new algorithm with the complexity O(logm) is presented to compute inverses in the finite field GF(2m) based on the normal basis representations and the Massey-Omura s multipliers. The inverse in GF(2m) can be computed with [log2(m-1)]+w(m-1)-1 multiplications and m-1 cyclic shifts, where [x] denotes the maximum integer less than or equal to x, w(m-1) the number of 1 in the binary representation of m-1. -
Berlekamp E R. Algebraic Coding Theory. New york: McGraw-Hill, 1968.[2]Brickell F F. A fast modular multiplication algorithm with application to two key cryptography, advances in cryptography. Proceedings of Crypto-82, New York: Plenum Press, 1983, 51-60.[3]Wang C C, Truong T K, Shao H M, Deutsch L J, Omura J K, Reed I S. VLSI architectures for computing multiplications and inverses in GF(2m)[J].IEEE Trans. on Computers.1985, C-34(8):709-716[4]徐大專(zhuān).在GF(2m)上計(jì)算指數(shù)和逆.計(jì)算機(jī)學(xué)報(bào),1990, 13(11): 860-863.[5]Itoh T, Tsujii S. Effective recursive algorithm for computing multiplicative inverses in GF(2m)[J].Electron. Lett.1988, 24(6):334-335[6]Asano Y, Itoh T, Tsujii S. Generalised fast algorithm for computing multiplicative inverses in GF(2m)[J].Electron. Lett.1989, 25(10):664-665 -
計(jì)量
- 文章訪問(wèn)數(shù): 3645
- HTML全文瀏覽量: 409
- PDF下載量: 558
- 被引次數(shù): 0
下載:
