论文部分内容阅读
在群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 that the interval size N in a group G is: Given g, h∈G, and a large integer N, an integer n (0≤n≤N) is found so that h = g ~ n. The solution is to improve the Pollard’s kangaroos method. Attempt to optimize the algorithm by reducing the number of jumps. At present, the optimal low-memory algorithm to solve this problem is the Pollard’s kangaroos method by Van Oorschot and Wiener. The average time cost is ( 2 + 0 (1)) √N subgroup operations.This paper improves the classical Pollard’s kangaroos method to solve this problem, and gets a new solution algorithm.The new algorithm is to use a multiple integer multiplication instead of a complete large integer multiplication Reduce the time cost of every kangaroos jump to improve the efficiency of the algorithm.Furthermore, by increasing the number of kangaroos, the algorithm improves both the number of jumps and the time cost of each jump, so as to obtain the discrete logarithm problem in the interval Effective solution to the algorithm.