GF(2m)에서 정규기저를 이용한고속 곱셈 역원 연산 방법

Cryptosystems have received very much attention in recent years as importance of information security is increased. Most of cryptosystems are defined over finite or Galois fields. In particular, the finite field is mainly used in public-key cryptosystems. These cryptosystems are constructed over finite field arithmetics, such as addition, subtraction, multiplication, and multiplicative inversion defined over. Hence, to implement these cryptosystems efficiently, it is important to carry out these operations defined over fast. Among these operations, since multiplicative inversion is much more time-consuming than other operations, it has become the object of lots of investigation. Recently, many methods for computing multiplicative inverses at high speed has been proposed. These methods are based on Fermat's theorem, and reduce the number of required multiplication using normal bases over . The method proposed by Itoh and Tsujii[2] among these methods reduced the required number of times of multiplication to. Also, some methods which improved the Itoh and Tsujii's method were proposed, but these methods have some problems such as complicated decomposition processes[3][5]. In practical applications, is frequently selected as a power of 2. In this paper, we propose a fast method for computing multiplicative inverses in , where . Our method requires fewer multiplications than the Itoh and Tsujii's method, and the decomposition process is simpler than other proposed methods.