Design of Iterative Divider in GF(2¹⁶³) Based on Improved Binary Extended GCD Algorithm

국문 초록 (Abstract)

본 논문에서는 표준기저(standard basis) 표기법을 이용하여 GF($2^{163}$) 상에서개선된 나눗셈 알고리듬을 제안하고, 제안한 알고리듬을 기반으로 한 반복 하드웨어 구조(iterative hardware structure)를 갖는 고속 나눗셈기를 설계한다. 제안한알고리듬은 이진 확장 GCD 알고리듬을 기본으로 하고 있으며, 모듈러감소 (modular reduction)를 위한 모든 산술연산은 기존의 방법과 달리 하나의 while루프 내에서 수행된다. 제안된 알고리듬을 기본으로 하여 설계된 나눗셈기는 모듈러 연산을 위한 각 모듈이 하나의 클럭에 의해서제어되므로 계산 속도가 매우 빠르다. 여기에서 사용하는 감소 다항식(reduction polynomial)은 SEC2 (Standards for Efficient Cryptography) 에서 권장하는 $f(x)=x^{163}+x^7+x^6+x^3+1$이며, 차수(degree) m은 163을 사용한다. 제안한 알고리듬은 Verilog HDL(Hardware Description Language)을 사용하여 FPGA로 구현되었으며, Xilinx-VirtexII XC2V8000 FPGA 상에서 85MHz로 동작함을 확인하였다. 또한, 구현 결과 및 성능 평가를 통하여 제안한 알고리듬의 종래의 두 알고리듬보다 성능이크게 개선됨을 보인다.

다국어 초록 (Multilingual Abstract)

In this paper, we first propose a fast division algorithm in GF($2^{163}$) using standard basis representation, and then it is mapped into divider for GF($2^{163}$) with iterative hardware structure. The proposed algorithm is based on the binary ExtendedGCD algorithm, and the arithmetic operations for modular reduction are performed within only one "while-statement" unlike conventional approach which uses two "while-statement". In this paper, we use reduction polynomial $f(x)=x^{163}+x^7+x^6+x^3+1$ that is recommended in SEC2(Standards for Efficient Cryptography) using standard basis representation, where degree m = 163. We also have implemented the proposed iterative architecture in FPGA using Verilog HDL, and it operates at a clock frequency of 85 MHz on Xilinx-VirtexII XC2V8000 FPGA device. From implementation results, we will show that computation speed of the proposed scheme is significantly improved than the existing two approaches.