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