Pollard ρ算法改进

• 作者: 李恒杰 王伟 胡建军
• 来源期刊: 计算机应用研究
• 关键词: 离散对数 复杂性 循环群 ρ形 循环查找
• 年，卷（期）: 2018,（7）
• 所属期刊栏目: 信息安全技术
• 页码范围: 2153-2155
• 页数: 3页
• 分类号: TP301.5
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2018.07.056

摘要

Pollard ρ(简称PR)算法基于Floyd的循环查找算法,是一种概率型算法,也是在有限循环群上计算离散对数的经典算法之一.概率型算法最大的缺点是计算的不确定性和盲目性,计算效率低.针对这一问题,利用数学工具推导出了ρ形的尾部长度的数学期望表达式,在此基础上,根据环上两个元素碰撞的特点,提出一种改进的PR算法,简称APR算法.APR算法利用ρ形的尾部长度的数学期望选择初始元素,提高初始元素落在环上的概率,又因为初始元素与环上另一元素碰撞的距离为它位置的两倍,APP算法提高了PR算法的碰撞概率,计算效率有了很大的提升,理论分析和数字验证表明,APR算法大大提高了PR算法的执行效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	胡建军	兰州文理学院数字媒体学院	16	29	3.0	4.0
2	李恒杰	兰州文理学院数字媒体学院	15	20	3.0	3.0
3	王伟	兰州文理学院数字媒体学院	5	4	2.0	2.0