- 유한체 $GF(2^m)$상의 나눗셈 알고리즘 설계
- ㆍ 저자명
- 안병규,An. Byeung-kyui
- ㆍ 간행물명
- 정보과학회논문지. Journal of KISS. 기술교육
- ㆍ 권/호정보
- 2005년|2권 1호|pp.48-52 (5 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
타원곡선 암호시스템을 $GF(2^m)$상에서 고속으로 구현하기 위해서는 빠른 나눗셈기가 필요하다. 본 논문에서는 유한체 $GF(2^m)$상에서 모듈러 나눗셈 A(x)/B(x) mod G(x)를 수행하는 나눗셈 알고리즘으로 빠른 나눗셈 구현에 적합한 알고리즘을 제안한다. 제안된 알고리즘은 이진 최대공약수(GCD) 알고리즘을 기반으로 $GF(2^m)$상의 나눗셈을 위한 바이너리 확장 GCD 알고리즘을 유도한 후 $GF(2^m)$상의 새로운 나눗셈 알고리즘을 구현한다. 본 논문에서 구현한 알고리즘은 기약 다항식(irreducible polynomial) 선택에 있어 어떤 제약도 두지 않고, 매우 규칙적이기 때문에 필드 크기 m에 대해 높은 유연성 및 확장성을 제공한다. 따라서 제안된 알고리즘은 FPGA구현에 적합하다.
To implement elliptic curve cryptosystem in $GF(2^m)$ at high speed, a fast divider is required. This paper a divide algorithm for computing modular division A(x)/B(x) mod G(x) in finite fields $GF(2^m)$. Based on the binary GCD(Greatest Common Divisor) algorithm and a modified version of the binary extended GCD algorithm, we design a new divide algorithm over finite field $GF(2^m)$. Furthermore, since this proposed algorithm does not restrict the choice of irreducible polynomial, and has a unidirectional data flow and has regularity and modularity, it provides a high flexibility and scalability with respect to the field size n Therefore, the proposed divide algorithm is well suited to the FPGA implementation.