유한체 에서 효율적으로 제곱근을 구하는 알고리즘들 (Efficient Computation of Square Roots in Finite Fields)

서지정보

· 발행기관 : 한국정보보호학회
· 수록지 정보 : 정보보호학회논문지 / 18권 / 6호 / 3 ~ 16페이지
· 저자명 : 한동국, 최두호, 김호원, 임종인

초록

본 논문에서는 확장체 (k 홀수) 에서 효율적으로 제곱근을 구하는 방법을 제안한다. 제곱근을 구하는 알고리즘은 표수 의 조건에 따라서 여러 가지 방법들이 제안되었다. 특히, 알고리즘을 구성하는 중심 되는 연산 중의 하나가 지수승 연산이다. 본 연구에서는 기존의 제곱근을 구하는 알고리즘에 사용되는 지수승의 지수들이 표수 p을 활용한 p-진법으로 표현할 경우, 특별한 형태의 주기성을 가지는 표현으로 나타내어짐을 증명하고, 이것을 활용해 기존의 알고리즘들을 효율적으로 계선하는 방법을 제안한다. 본 논문에서 제안한 방법은 표수 p의 조건에 의존하지 않고, 지수승 기반의 기존의 모든 제곱근 알고리즘에 적용 가능하다는 장점을 가지고 있다. 지금까지 알려진 바로는, 본 논문이 처음으로 Tonelli- Shanks 알고리즘을 효율적으로 개선하였으며, p≡1 (mod 16)인 경우 60% 이상의 효율성 증대가 있었다. 다른 제곱근 알고리즘에 적용한 결과들도 비교표들을 이용해 언급되어 있으며, 기존의 방법들에 비해 상당히 효율적임을 나타내고 있다.

영어초록

In this paper we study exponentiation in finite fields (k is odd) with very special exponents such as they occur in algorithms for computing square roots. Our algorithmic approach improves the corresponding exponentiation independent of the characteristic of . To the best of our knowledge, it is the first major improvement to the Tonelli-Shanks algorithm, for example, the number of multiplications can be reduced to at least 60% on average when p≡1 (mod 16). Several numerical examples are given that show the speed-up of the proposed methods.

참고자료

· 없음