有限域GF (2m)上的一个新的求逆算法
A NEW ALGORITHM FOR COMPUTING INVERSES IN THE FINITE FIELD GF(2m)
-
摘要: 根据有限域GF(2m)上的正规基表示和Massey-Omura乘法器,本文提出了一个复杂性为O(logm)的求逆算法。新算法完成一次求逆运算只需要[log2(m-1)]+w(m-1)-1次乘法和m-1次循环移位,这里[x]表示小于等于x的最大整数,w(m-1)表示m-1的二进制表示中1的个数。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]徐大专.在GF(2m)上计算指数和逆.计算机学报,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 -
计量
- 文章访问数: 3598
- HTML全文浏览量: 397
- PDF下载量: 552
- 被引次数: 0
下载:
