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

• 作者: 吕克伟 王瑶
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: 离散对数(DLP) Pollard's kangaroos method Pollard's rho method 区间 时间代价
• 年，卷（期）: 2015,（6）
• 页码范围: 570-582
• 页数: 13页
• 分类号: TP309.7
• 字数: 9909字
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000103

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王瑶	中国科学院信息工程研究所	23	348	9.0	18.0
2	吕克伟	中国科学院信息工程研究所	9	17	3.0	4.0