유한체 $GF(2^m)$상의 나눗셈 알고리즘 설계 = Design of Divide Algorithm Over Finite Field $GF(2^m)$

국문 초록 (Abstract)

타원곡선 암호시스템을 $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구현에 적합하다.