NAF와 타입Ⅱ 최적정규기저를 이용한 GF(2n)상의 효율적인 지수승 연산 (NAF and Optimal Normal Basis of TypeⅡ and Efficient Exponentiation in GF(2n))

서지정보

· 발행기관 : 한국통신학회
· 수록지 정보 : 한국통신학회논문지C / 34권 / 1호 / 21 ~ 27페이지
· 저자명 : 권순학, 구남훈, 김창훈, 고병환

초록

지수의 signed digit representation을 사용하여 타입 II 최적정규기저에 의해 결정되는 GF(2n)상의 효율적인 지수승 알고리즘을 제안한다. 제안하는 signed digit representation은 GF(2n)에서 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(2n) 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(2n). 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.

참고자료

· 없음