一种组合Pohlig-Hellman和Pollard ρ的迭代求解离散对数方法

An iterative method based on Pohlig-Hellman and Pollard ρ for computing discrete logarithm

Pohlig-Hellman算法的优点是计算速度快,缺点是需要群的阶是光滑的.Pollard ρ算法的优点是不受群结构的限制,缺点是属于概率算法,计算的准确性低于Pohlig-Hellman算法.学者很少关注Pollard ρ和Pohlig-Hellman两个算法的有效融合,针对这一问题,结合两个算法各自的长处,提出一种基于Pohlig-Hellman的Pollard ρ混合离散对数迭代求解算法.算法的思想是:当阶的素因子小于等于光滑界时,使用Pohlig-Hellman算法迭代计算;当阶的素因子大于光滑界时,使用Pollard ρ算法迭代计算.同时分析了混合算法的计算效率.最后通过实例验证了结论的正确性和有效性.

The advantage of the Pohlig-Hellman algorithm is that the calculation speed is fast,but the disadvantage is that the order of the group requires to be smooth. The advantage of Pollard ρ algorithm is that it is not limited to the group structure,but the disadvantage is the probability algorithm, and the accuracy of calculation is usually lower than the Pohlig-Hellman algorithm. Scholars paid little attention to effective fusion of both Pollard ρ and Pohlig-Hellman algorithms. In order to solve the problem, combined with the respective strengths of the two algorithms, the paper put forward a kind of Pollard ρ mixed discrete logarithm iteration algorithm based on Pohlig-Hellman. The idea of the algorithm was that the Pohlig-Hellman algorithm was used to iterate when the order factor was less than or equal to the smooth boundary, and the Pollard ρ algorithm was used to iterate when the order factor was greater than the smooth boundary. At the same time, the computational efficiency of the hybrid algorithm was analyzed, and the correctness and validity of the algorithm and the analysis results were verified by an example.