:: The Journal of the Institute of Internet, Broadcasting and Communication ::, Vol.17 No.3 | (2017) pp.1~7
큐를 이용한 이산대수의 사이클 검출
Abstract
본 논문은 에서 를 구하는 Pollard의 Rho와 Brent의 이산대수 알고리즘의 수행횟수를 크게 감소시키는 알고리즘을 제안하였다. 제안된 방법은 Brent 방법으로 충돌을 검출하였다. 차이점은 대신 을, 대신 크기가 10인 Queue에 를 저장하는 방법을, 대신 의 충돌을 찾는 방법을 적용하였다. 제안된 Queue 적용법은 로 의 충돌을 검출하는 Pollard의 Rho 알고리즘의 수행횟수를 , 으로 의 충돌을 검출하는 Brent 알고리즘의 수행횟수를 감소시켰다.
This paper proposes a discrete logarithm algorithm that largely reduces execution times of Pollard's Rho and Brent's algorithm in obtaining from . The proposed algorithm can be distinguished from the conventional Brent’s algorithm by three major features: it sets an initial value as in lieu of ; replaces pointer with for a Queue the size 10; and detects collision of instead of . This Queue method has reduced the execution time of Pollard's Rho algorithm with by , and that of Brent's algorithm with by .
discrete logarithm,Pollard Rho algorithm,Brent Algorithm,queue,stack
