5.5 Pollard’s Method
我们已经在 注 5.43 中提到，碰撞算法一般都需要大量的内存空间用于数据的存储，但 Pollard 提出了一个美妙的想法使得我们只需要进行一点点额外的运算就可以省去绝大部分用于数据存储的内存空间。在这一节中我们将介绍该算法背后的基础思想，并通过解决一个在 𝕡 下的离散对数问题来进行说明。
5.5.1 Abstract Formulation of Pollard’s Method
抽象的公式从一个抽象的定义开始，我们设 喂一个有限集合，且设函数 能够很好的扰乱 中的元素。假设我们从一些元素 开始，然后不断地对其使用函数 ，我们就可以得到一个序列
从 到 自身地映射 就是 离散动力系统（discrete dynamical system） 的一个例子，序列
如果集合 是有限的，那么 中的某些元素一定会在 中出现两次。我们用图 5.1 来刻画这样的轨道：
![密码学 ｜ 5.5 Pollard’s p Method]()
Figure 5.1: Pollard’s ρ method
当还在点 时，它们沿着一条路径“前进”，直到出现重复的元素后开始进入循环，绕着环路移动。如图所示，在到达循环之前，我们设 是“尾部”中元素的数量，设 是循环中元素的数目。数学上的定义为：
注5.47
图5.1 可能会让你想起希腊字母 。因此，基于离散动力系统元素轨道的碰撞算法被称为 算法。第一个 算法是由 Pollard 于1974年发明的。
假设 包含 个元素，根据接下来我们将介绍的 定理 5.48 ，我们将给出证明 通常不大于 的一个小倍数。那么根据定义 ，我们将在 中得到一个碰撞。然而，因为我们不知道具体的 和 ，因此为了获得碰撞，按理说我们需要构造一个序列 。
Pollard 想法的精妙之处在于，存在一种可能，即便我们不存储所有的值，我们也可能获得碰撞。有很多种方法对此进行解释，我们选择一种通俗易懂（即便不是最高效的）的进行说明。该想法就是，我们不仅仅只计算序列 ，我们还计算第二个序列 ，定义为
即，每当我们计算 的 映射以计算 ，我们就对 计算两次映射，因此显然我们有
那么，大概需要多久我们才能够获取 值满足 呢？设 ，我们有
根据图 5.1 我们就可以很清楚知道，由于我们获得了碰撞 ，那么 肯定是经过了 ，即 ; 并且此时 也已经在循环中经过了 若干次，即 是 的倍数。
因此，当且仅当 并且 ，我们有 。第二个条件意味着 ，因此，当 第一次为 的倍数且大于 时，我们就能获得碰撞。所以如果 存在可以被 整除的数话，那么就能证明存在 满足
在接下来介绍的定理中，我们将给出结论 大约为 ，因此在 的小倍数步内，我们有很大的机会获得碰撞。这与我们在5.4.3一节介绍的算法的时间复杂度是一个量级的，但是注意到我们仅仅储存了两个数字，序列 和 的当前值 。
定理 5.48 （Pollard’s Method：abstract version）
设 为包含 个元素的有限集合，存在映射 ，初始值 。
1. 设有“前进轨道” 尾部长为 ，循环结长度为 ，如图 5.1 所示，那么有
(5.34)x2i=xi for some 1≤i<T+M
于是根据 5.34 式，我们期望在 步内找到碰撞，其中一 “步” 表示一次映射的计算。
-
-
这里我们仅简述一下（2）的证明，因为它将概率论和算法分析相结合。然而，希望得到严格证明的读者还需要补充一些细节。假设我们已经计算了前 个值，但我们没有得到任何碰撞的概率是多少？设映射足够随机， 则可以看作是从集合 中随机选择的，那么我们可以以此计算概率为
式 5.35：由于需要满足前 个值 都是不同的，那么对于 来说，在 个可能的选择中，还剩 个 值与前面的值不同。因此获得一个新的与前值均不同的值的概率为 。
对于式 5.36，我们可以使用近似 对于 较小时该近似成立。实践中一般 较大并且 约为 ，因此对于 , 满足要求。于是
(5.37)Pr(xi均不相同)=∏i=1k−1e−i/N=e−(1+2+⋯+(k−1))/N≈e−k2/2N
现在我们已经知道了 均不相同的概率，那么下一个值 能够产生碰撞的概率是多少呢？这里存在 个值可以发生碰撞，因此概率为
(5.38)Pr(xk能够产生碰撞|x0,…,xk−1均不同)=kN
(5.39)E(第一次产生碰撞)=∑k≥1k⋅Pr(xk是第一次产生碰撞)≈∑k≥1k2N⋅e−k2/2N
我们想知道这个级数作为 的函数是什么样子的，于是有了下面的推导（使用了一点初等微积分）。
引理 5.49
设 是一个 “表现良好” 的实数函数，并且具有 收敛，那么对于大数 ，我们有
(5.40)∑k=1infinF(kn)≈n⋅∫0infinF(t)dt
证明：我们从 在区间 上的定积分开始。根据定义，该积分等于黎曼和的极限
其中求和部分将区间 划分为 块。实际上，如果 足够大，那么有
那么如果 ，则有式子 5.40 （这并不认为这是一个严格的论证，其目的仅仅是传达潜在的想法）
对于最后一行定积分的计算我们用了近似，尽管实际上是可以精确计算的，其值为 。于是这就完成了（2）的证明，结合（1）和（2）我们给出了定理5.48的最终陈述。
注 5.50
我们有必要用检验一下定理 5.48 所用估计的准确性，在该证明中，我们提到当 较大时，我们找到碰撞的期望步数由下列三式之一给出：
更准确地说， 是精确的公式，但如果 非常大，则很难精确计算，而 和 是近似值。我们计算了一些中等大小的 值的 、和 值，并将结果汇编在表5.10中。如表所示， 和 非常接近，当 变得相当大，它们也很好的与 近似。因此，对于非常大的 ，例如，使用 估计 是非常合理的。
![密码学 ｜ 5.5 Pollard’s p Method]()
Table 5.10: Expected number of steps until a ρ collision
评论