A fast algorithm for computing multiplicative inverses in GF(2m) using normal bases

This paper proposes a fast algorithm for computing multiplicative inverses in GF(2 m ) using normal bases. Normal bases have the following useful property: In the case that an element x in GF(2 m ) is represented by normal bases, 2 k power operation of an element x in GF(2 m ) can be carried out by k times cyclic shift of its vector representation. C. C. Wang et al. proposed an algorithm for computing multiplicative inverses using normal bases, which requires (m − 2) multiplications in GF(2 m ) and (m − 1) cyclic shifts. The fast algorithm proposed in this paper also uses normal bases, and computes multiplicative inverses iterating multiplications in GF(2 m ). It requires at most 2[log2(m − 1)] multiplications in GF(2 m ) and (m − 1) cyclic shifts, which are much less than those required in the Wang's method. The same idea of the proposed fast algorithm is applicable to the general power operation in GF(2 m ) and the computation of multiplicative inverses in GF(q m ) (q = 2 n ).

Authors

• Toshiya Itoh
• Shigeo Tsujii

Keywords

No keywords are indexed for this paper.