摘要
Pollard rho(简称PR)算法基于Floyd的循环查找算法,是一种概率型算法,也是在有限循环群上计算离散对数的经典算法之一.针对已有研究很少关注PR算法的执行效率,借助已有研究成果,经过大量的实验数据,分析了PR算法运行效率的差异,并指出不同有限循环群的迭代函数以及随机游走的初始点选择应该有所不同.也就是说,PR算法应根据不同的群设计相应的迭代函数和选择适当的初始点.实验数据表明,当某个迭代函数的效率较低时,通过改变迭代函数的划分空间或者初始游走位置,算法的效率可以大幅度提升.
Based on a cycle-finding algorithm of Floyd,Pollard rho（PR）algorithm is a probabilistic model algorithm and also one of the classical algorithm of computing discrete logarithm on cyclic group.Few studies of the past focused on the execution efficiency of PR algorithm,therefore,with the aid of existing research results,through a large number of experimental data,this paper analyzes the differences of the PR algorithm efficiency,and points out that the iterative function and initial random walk point of different finite cyclic should be different.In other words,the PR algorithm should design the corresponding iteration function and select the appropriate initial points according to the different groups.Experimental data show that when an iterative function of efficiency is low,by changing dividing space of the iteration function or initial point,the efficiency of the algorithm can greatly be enhanced.
出处
《兰州文理学院学报（自然科学版）》
2018年第1期62-66,共5页
Journal of Lanzhou University of Arts and Science(Natural Sciences)
基金
甘肃省高等学校科学研究项目(2015B-136)
关键词
离散对数
复杂性
循环群
ρ形
循环查找
discrete logarithm
complexity
cyclic group
p shaped
cycle-finding
