큐를 이용한 이산대수의 사이클 검출 (Cycle Detection in Discrete Logarithm Using a Queue)

서지정보

· 발행기관 : 한국인터넷방송통신학회
· 수록지 정보 : 한국인터넷방송통신학회 논문지 / 17권 / 3호 / 1 ~ 7페이지
· 저자명 : 이상운

초록

본 논문은 에서 를 구하는 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 .

참고자료

· 없음