earticle

영어

Until now, Pollard's Rho algorithm has been known as the most efficient way for discrete algebraic problems to decrypt symmetric keys. However, the algorithm is being studied on how to further reduce the complexity of O( p ) performance, along with the disadvantage of having to store the giant stride m = 「 p 」 data. This paper proposes an array method for cycle detection in discrete logarithms. The proposed method reduces the number of updates of stack memory by at least 73%. This is done by only updating the array when ( xi < 0.5xi-1) ∩ (xi < 0.5(p-1)). The proposed array method undergoes the same number of modular calculation as stack method, but significantly reduces the number of updates and the execution time for array through the use of a binary search method.

한국어

지금까지는 Pollard의 Rho 알고리즘이 대칭키의 암호를 해독하는 이산대수 문제에 대해 가장 효율적인 방법으 로 알려져 있다. 그러나 이 알고리즘은 거인걸음 보폭 m = 「 p 」개의 데이터를 저장해야 하는 단점과 더불어 O( p ) 수행 복잡도를 보다 감소시킬 수 있는 방법에 대한 연구가 진행되고 있다. 본 논문은 이산대수의 사이클 검출을 위한 Nivasch의 스택 법의 데이터 갱신 횟수를 73% 이상 감소시키는 배열법을 제안하였다. 제안된 방법은 배열을 적용하였으며, ( xi < 0.5xi-1) ∩ (xi < 0.5(p-1)) 인 경우에 한해 배열 값을 갱신하는 방법을 적용하였다. 제안된 방법은 스택법과 동일한 모듈러 연산횟수를 보였지만 스택 법에 비해 이진탐색 법을 적용하여 배열 갱신 횟수와 탐색 시간을 획기적으로 감소시켰다.