Improved Algorithm for Solving Discrete Logarithm Problem by Expanding Factor

The discrete logarithm problem(DLP)is to find a solution n such that g^n=h in a finite cyclic group G=,where h∈G.The DLP is the security foundation of many cryptosystems,such as RSA.We propose a method to improve Pollard’s kangaroo algorithm,which is the classic algorithm for solving the DLP.In the proposed algorithm,the large integer multiplications are reduced by controlling whether to perform large integer multiplication.To control the process,the tools of expanding factor and jumping distance are introduced.The expanding factor is an indicator used to measure the probability of collision.Large integer multiplication is performed if the value of the expanding factor is greater than the given bound.The improved algorithm requires an average of(1.633+o(1))q(1/2)times of the large integer multiplications.In experiments,the average large integer multiplication times is approximately(1.5+o(1))q(1/2).