平行Pollard的Rho：杰出点数

当对离散日志使用并行版本的Pollard的Rho算法时，每个处理器都会执行自己的随机游走以找到可区分的点，并将起点和可区分的点报告给服务器。如果两个处理器报告相同的可分辨点，则服务器可以重新进行随机游走并查找发生碰撞的位置并求解离散对数。区别点取决于区别位数。平均而言，它是$ 2 ^ d $，其中$ d $是可区分的位数。 ，则有可能在不使每个处理器接近$ 2 ^ d $迭代的情况下得出所需数量的可分辨点。

我们有一个128位离散日志问题。我们需要〜$ 2 ^ {64} $组元素来解决它。我们可以用$ 2 ^ {32} $个具有$ 32 $个专有位的专有点来做到这一点。

我们假设使用了500亿个处理器，每个处理器每秒执行20个步骤（每秒生成一万亿个积分） 。

这就是〜$ 2 ^ {40}（\ dfrac {1} {2 ^ {32}}）$ =每秒$ 256 $可分辨点。

它大约需要194天才能找到$ 2 ^ {32} $显着点。小于预期的$ 2 ^ {32} $。

这意味着报告给服务器的每个可分辨点最多代表所采取的步骤$ 369,782,000 $。因此，起点和显着点之间的总点数远远少于$ 2 ^ {64} $

问题：

这是否意味着需要的数量远远超过$ 2 ^ {32} $杰出点数？

我认为这是因为报告的总点数不足以导致发生碰撞的可能性。我们可以说每个可分辨的点代表$ 2 ^ {32} $点，但是由于走动非常短，因此发生碰撞的可能性更大，是一个随机走动进入另一个随机走动的起点的结果碰撞是没有用的（在文献中称其为“罗宾汉”）。或许多步履蹒跚的慢速处理器（较少的显着位，更多的显着点）和大量存储。