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% 감소시켰다.