일반기술

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

본 기술은 유한체에서 역수를 구하는 새로운 알고리즘을 이용하여 2n 비트 프로세서를 갖는 컴퓨터에서 효과적으로 역수를 계산하는 방법에 관한 것이다.GF(pm)에서 역수를 계산하는 고전적인 알고리즘은 다항식에 대한 확장된 유클리드 알고리즘이며, GF(2m)에서 효과적이도록 개선한 알고리즘으로는 준역수알고리즘이 있지만, 이들 알고리즘은 p가 큰 수일 때는 확장된 유클리드 알고리즘보다 비효율적이라는 문제가 있었다.반면, 본 기술에서는 기존의 AIA(Almost Inverse Algorithm)를 개선하여 p=2n-c(c:작은 양의 정수)에 대하여 수정된 AIA를 이용하고, 유한체의 두 원소의 최고차항의 차수가 동일한 경우 단축된 단계를 수행하는 수정된 AIA를 이용하는 역수 계산 방법을 구현할 수 있다본 기술에 의한 유한체에서의 효과적인 역수 계산 방법은 GF(pm)의 두 원소 F=a(x)와 G=f(x)에서, 모듈라 f(x)에 대한 a(x)으 역수 a-1(x)를 계산하는 방법에 있어서, (ⅰ)반복연산횟수에 따른 연산계수 k=0, B=1, C=0으로 설정하고, 두 원소를 취하는 단계, (ⅱ)F가 x로 나누어지면, F=F/x(F를 x로 나눈 몫), C=C, x, k=k+1로 수정하는 작업을 F가 x로 나누어지지 않을 때까지 반복 수행하는 단계, (ⅲ)다항식의 F의 최고차수인 deg(F)가 0인가를 판단하여, deg(F)=0이면, k와 c(x)=B, (F0-1mod p)를 출력하고 작업을 종료하는 단계, (ⅳ)deg(F)=0이 아니면, deg(F)<deg(G)인지를 판단하여, deg(F)<deg(G)이면 F와 G를 바꾸고 B와 C를 바꾸는 단계 및 (ⅴ)위의 결과에 따라서, F와 G의 상수항과 최고차항을 소거한 후, 위의 단계(ⅱ)로 진행하는 단계로 이루어져 있다.이와 같이 이루어진 본 기술에 의하면, 상대적으로 많은 시간이 소요되는 곱셈에 대한 역수 계산과 유한체 GF(pm)에서 p가 큰 수일 때 역수 계산이 비효율적으로 되는 단점을 해결할 수 있는 효과가 있다