作者：王瑶; 吕克伟kangaroosmethodrho区间时间代价
摘要：在群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的数量使得算法在跳跃次数和每次跳跃的时间代价两方面都得到改进,从而得到区间上离散对数问题的更有效的求解算法.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
