论文研究Pollardρ算法改进.pdf

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