Multiple Parallel-Pollard's Rho Discrete Logarithm Algorithm
Sang-Un Lee · Journal of the Korea Society of Computer and Information · 2015
This paper proposes a discrete logarithm algorithm that remarkably reduces the execution time of Pollard's Rho algorithm. Pollard's Rho algorithm computes congruence or collision of ${\alpha}^a{\beta}^b{\equiv}{\alpha}^A{\beta}^B$ (modp) from the initial value a = b = 0, only to derive ${\gamma}$ from $(a+b{\gamma})=(A+B{\gamma})$ , ${\gamma}(B-b)=(a-A)$ . The basic Pollard's Rho algorithm computes $x_i=(x_{i-1})^2,{\alpha}x_{i-1},{\beta}x_{i-1}$ given ${\alpha}^a{\beta}^b{\equiv}x$ (modp), and the general algorithm computes $x_i=(x_{i-1})^2$ , $Mx_{i-1}$ , $Nx_{i-1}$ for randomly selected $M={\alpha}^m$ , $N={\beta}^n$ . This paper proposes 4-model Pollard Rho algorithm that seeks ${\beta}_{\gamma}={\alpha}^{\gamma},{\beta}_{\gamma}={\alpha}^{(p-1)/2+{\gamma}}$ , and ${\beta}_{{\gamma}^{-1}}={\alpha}^{(p-1)-{\gamma}}$ ) from $m=n={\lceil}{\sqrt{n}{\rceil}$ , (a,b) = (0,0), (1,1). The proposed algorithm has proven to improve the performance of the (0,0)-basic Pollard's Rho algorithm by 71.70%.