在这一节中,我们将讨论如何使用 Pollard’s ρ Method 解决如下离散对数问题,其中 是 下的一个原根。想法是找到 和 的碰撞,然后我们就有 ,有这样的关系离解决这个离散对数问题就不远了。问题在于扰乱函数 的选取,其需要能够很好地将 中的元素扰乱,但是又比较简单,这样方便追踪其轨道。 Pollard 在 《Monte Carlo methods for index computation (mod p)》给出建议需要注意的是在使用式 时需要将 取余 到区间 中,
注 5.51 其实并没有人能够证明式 是足够随机的以确保定理 能够适用,但是在实践中 表现效果还是不错的。不过, Teske 在《Speeding up Pollard’s rho method for computing discrete logarithms, in Algorithmic Number Theory》 和 《 Square-root algorithms for the discrete logarithm problem (a survey), in Public-Key Cryptography and Computational Number Theory》 表明 并没有很好的随机性以给出最佳效果,并且她还给出了一些更复杂的函数例子,称在这些函数中 Pollard’s ρ Method 工作的很好。