关于区间上离散对数问题的改进算法

Improved Method on the Discrete Logarithm Problem in an Interval

在群G上区间大小为N的离散对数问题为:给定g,h∈G以及大整数N,找到整数n(0≤n≤N),使得h=g^n,人们对于该问题的求解主要是对Pollard's kangaroos method的改进,尝试通过减少跳跃次数来优化算法,目前解决这一问题的最优低存储算法是Van Oorschot和Wiener版本的Pollard's kangaroos method,其平均情况下的时间代价是(2+0(1))√N次群运算.文中对解决这一问题的经典Pollard's kangaroos method进行改进得到新的求解算法.新算法是通过利用多次小整数乘法代替一次完整的大整数乘法来减少kangaroos每次跳跃的时间代价实现算法效率的提高.进一步,文中通过增加kangaroos的数量使得算法在跳跃次数和每次跳跃的时间代价两方面都得到改进,从而得到区间上离散对数问题的更有效的求解算法.

The discrete logarithm problem in an interval of size N in a group G is:Given g,h∈G and an interval N to find an integer n(0≤n≤N),if it exists,so that h=g^n holds.Many methods have been designed to solve this problem which of the most common one being the improved method of the Pollard's kangaroos method.The improved method is mainly to optimize the algorithm by reducing the number of jumps which always need a complete large multiplication.Previously the best low-storage algorithm to solve this problem was the Van Oorschot and Wiener version of the Pollard's kangaroos method.The heuristic average case running time of this method is(2+0(1))√(N) group operations.We present a new method for the problem which is based on the Pollard's kangaroos method.The new method improved the efficiency of the method by reducing the time cost of each jump with many small integer multiplications instead of a complete large integer multiplication.Further,we increase the number of kangaroos to make our method more effective in two aspects which are the number of jumps and the time cost of each jump.The new method gave a more effective method to solve the discrete logarithm problem in an interval.