Earticle

초록

영어

The problem of finding γ in α2 ≡β(mod p) given α,β,p is called a discrete logarithm. Here, β in which a different value is shown up to a specific value γ, but the same value is forms a block repeated thereafter. It takes a form similar to the Greek letter p(rho), and Pollard named it the rho(p) algorithm.This paper proposes a dual Array method for cycle detection in discrete logarithms. The method I propose markedly reduces the number of updates when compared to x2𝑖 pointer of Pollard's Rho, Brent's 𝑥𝑖 ,( i=2k) pointer, and Nivasch's stack method. This method also reduces the number of modular computation of Nivasch's stack method by 22.90% and the number of memory comparison by 80.02%.

한국어

α2 ≡β(mod p)에서 α,β,p가 주어졌을 때 γ을 구하는 문제를 이산대수라 한다. 여기서 β는 특정 γ값 까지는 다른값을 보이지만 그 이후부터는 동일한 값이 반복되는 블록을 형성한다. 이는 그리스 문자 p를 닮은 형태를 취하여 Pollard는 p 알고리즘이라고 명명하였다. 본 논문은 이산대수의 사이클 검출을 위해 이중 배열법을 제안하였다. 제안된 이중 배열법은 Pollard의 Rho 𝑥2𝑖 포인터 법, Brent의 𝑥𝑖 ,( i=2k) 포인터법과 Nivasch의 스택 법에 비해 배열 값비교와 갱신 횟수를 크게 감소시켰다. 제안된 알고리즘은 Nivasch의 스택 법에 비해 모듈러 연산횟수는 22.90%, 메모리 비교횟수는 80.02% 감소시켰다.

목차

요약
Abstract
Ⅰ. 서론
Ⅱ. 이산대수의 사이클 검출
Ⅲ. 이중 배열 법
Ⅳ. 실험 결과 및 분석
Ⅴ. 결론
References

키워드

저자

• 이상운 [ Sang-Un Lee | 정회원, 강릉원주대학교 과학기술대학 멀티미디어공학과 ] Corresponding Author

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국인터넷방송통신학회 논문지 [The Journal of the Institute of Internet, Broadcasting and Communication]

• 간기

  격월간

• pISSN

  2289-0238

• eISSN

  2289-0246

• 수록기간

  2001~2025

• 십진분류

  KDC 326 DDC 380