지수의 signed digit representation을 사용하여 타입 II 최적정규기저에 의해 결정되는 $GF(2^n)$상의 효율적인 지수승 알고리즘을 제안한다. 제안하는 signed digit representation은 $GF(2^n)$에서 non-adjacent form(NAF)를 사용한다. 일반적으로 signed digit representation은 정규기저가 주어진 경우 사용하기 어렵다. 이는 정규 원소의 역원연산이 상당한 지연시간을 갖기 때문이다. 반면에 signed digit representation은 다항식 기저를 이용한 체에 쉽게 적용가능하다. 하지만 본 논문의 결과는 타입 II 최적정규기저(optimal normal basis, ONB), 라는 특별한 정규 기저가 지수의 signed digit representation을 이용한 효율적인 지수승 연산에 이용될 수 있음을 보인다.
We present an efficient exponentiation algorithm for a finite field $GF(2^n)$ determined by an optimal normal basis of type II using signed digit representation of the exponents. Our signed digit representation uses a non-adjacent form (NAF) for $GF(2^n)$. It is generally believed that a signed digit representation is hard to use when a normal basis is given because the inversion of a normal element requires quite a computational delay. However our result shows that a special normal basis, called an optimal normal basis (ONB) of type II, has a nice property which admits an effective exponentiation using signed digit representations of the exponents.
