Pollard rho算法特征研究

作者：胡建军; 王伟; 李恒杰

来源：兰州文理学院学报(自然科学版), 2018, 32(01): 62-66.

DOI：10.13804/j.cnki.2095-6991.2018.01.015

• 离散对数
• 复杂性
• 循环群
• ρ形
• 循环查找

Pollard rho(简称PR)算法基于Floyd的循环查找算法,是一种概率型算法,也是在有限循环群上计算离散对数的经典算法之一.针对已有研究很少关注PR算法的执行效率,借助已有研究成果,经过大量的实验数据,分析了PR算法运行效率的差异,并指出不同有限循环群的迭代函数以及随机游走的初始点选择应该有所不同.也就是说,PR算法应根据不同的群设计相应的迭代函数和选择适当的初始点.实验数据表明,当某个迭代函数的效率较低时,通过改变迭代函数的划分空间或者初始游走位置,算法的效率可以大幅度提升.

• 单位
  兰州文理学院