일반기술

유한체 GF(p)에서의 효과적인 역수 계산 방법

본 기술은 유한체에서의 효과적인 역수 계산 방법에 관한 것으로, 보다 상세하게는 유한체에서 역수를 구하는 새로운 알고리즘을 이용하여 2n 비트 프로세서를 갖는 컴퓨터에서 효과적으로 역수를 계산하는 방법에 관한 것으로, 기존의 AIA를 개선하여, 특히 p=2n-c (c:작은 양의 정수)에 대하여 수정된 AIA(Modified Almost Inverse Algorithm; MAIA)를 이용한 유한체에서의 효과적인 역수 계산 방법을 제공하는 데 있다. 본 기술이 이루고자 하는 다른 기술적 과제는 유한체의 두 원소의 최고차항의 차수가 동일한 경우 단축된 단계를 수행하는 수정된 AIA(Modified Almost Inverse Algorithm; MAIA)를 이용한 유한체에서의 효과적인 역수 계산 방법을 제공하는데 있다.본 기술의 유한체에서의 효과적인 역수 계산 방법은 GF(pm)의 두 원소 F=a(x)와 G=f(x)에서, 모듈라 f(x)에 대한 a(x)의역수 a-1 (x)를 계산하는 방법으로 i) 반복연산횟수에 따른 연산계수 k=0, B=1, C=0으로 설정하고, 두 원소를 취하는 단계; ii) F가 x로 나누어지면, F=F/x (F를 x로 나눈 몫), C=C·x, k=k+1로 수정하는 작업을 F가 x로 나누어지지 않을 때까지 반복 수행하는 단계; iii) 다항식 F의 최고차수인 deg(F)가 0인가를 판단하여, deg(F)=0이면, k와 c(x)=B·(F0-1 mod p)를 출력하고 작업을 종료하는 단계; iv) 단계 iii)에서 deg(F)=0이 아니면, deg(F)＜deg(G)인지를 판단하여, deg(F)＜deg(G)이면 상기 F와 G를 바꾸고 B와 C를 바꾸는 단계; 및 v) 단계 iv)의 결과에 따라서, 상기 F와 G의 상수항과 최고차항을 소거한 후, 단계 ii)로 진행하는 단계를 포함한다. 이로써, 본 기술은 기존의 EEA와 AIA를 결합하여 역수 연산을 빠르고 효율적으로 수행하여, 상대적으로 많은 시간이 소요되는 곱셈에 대한 역수 계산과 유한체 GF(pm)에서 p가 큰 수 일 때 역수계산이 비효율적으로 되는 단점을 해결하였다. 상술한 바와 같이, 본 기술의 유한체에서의 효과적인 역수 계산 방법은, 상대적으로 많은 시간이 소요되는 곱셈에 대한역수 계산과 유한체 GF(pm)에서 p가 큰 수 일때 역수계산이 비효율적으로 되는 단점을 해결하고 있다. 이로써, 본 기술은 기존의 EEA와 AIA를 결합하여 역수 연산을 빠르고 효율적으로 수행할 수 있다.