密码学｜ 5.5 Pollard’s p Method

密码学 2年前 (2023) admin

389 0 0

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) x 2 i = x i f o r s o m e 1 \leq i < T + M$

2.如果映射的随机性足够好，那么具有期望：

于是根据 5.34 式，我们期望在步内找到碰撞，其中一 “步” 表示一次映射的计算。

证明：

这一部分我们已经在前面证明过了。
这里我们仅简述一下（2）的证明，因为它将概率论和算法分析相结合。然而，希望得到严格证明的读者还需要补充一些细节。假设我们已经计算了前个值，但我们没有得到任何碰撞的概率是多少？设映射足够随机，则可以看作是从集合中随机选择的，那么我们可以以此计算概率为

式 5.35：由于需要满足前个值都是不同的，那么对于来说，在个可能的选择中，还剩个值与前面的值不同。因此获得一个新的与前值均不同的值的概率为。

对于式 5.36，我们可以使用近似对于较小时该近似成立。实践中一般较大并且约为，因此对于 , 满足要求。于是

$(5.37) P r (x i 均不相同) = \prod i = 1 k - 1 e - i / N = e - (1 + 2 + \dots + (k - 1)) / N \approx e - k 2 / 2 N$

由于相对较大，于是使用了近似

现在我们已经知道了均不相同的概率，那么下一个值能够产生碰撞的概率是多少呢？这里存在个值可以发生碰撞，因此概率为

$(5.38) P r (x k 能够产生碰撞 | x 0, \dots, x k - 1 均不同) = k N$

于是有

那么第一次找到碰撞的期望步数则为

$(5.39) E (第一次产生碰撞) = \sum k \geq 1 k \cdot P r (x k 是第一次产生碰撞) \approx \sum k \geq 1 k 2 N \cdot e - k 2 / 2 N$

我们想知道这个级数作为的函数是什么样子的，于是有了下面的推导（使用了一点初等微积分）。

引理 5.49

设是一个 “表现良好” 的实数函数，并且具有收敛，那么对于大数，我们有

$(5.40) \sum k = 1 infin F (k n) \approx n \cdot \int 0 infin F (t) d t$

证明：我们从在区间上的定积分开始。根据定义，该积分等于黎曼和的极限

其中求和部分将区间划分为块。实际上，如果足够大，那么有

那么如果，则有式子 5.40 （这并不认为这是一个严格的论证，其目的仅仅是传达潜在的想法）

我们使用引理 5.49 进行估计

对于最后一行定积分的计算我们用了近似，尽管实际上是可以精确计算的，其值为。于是这就完成了（2）的证明，结合（1）和（2）我们给出了定理5.48的最终陈述。

注 5.50

我们有必要用检验一下定理 5.48 所用估计的准确性，在该证明中，我们提到当较大时，我们找到碰撞的期望步数由下列三式之一给出：

更准确地说，是精确的公式，但如果非常大，则很难精确计算，而和是近似值。我们计算了一些中等大小的值的和值，并将结果汇编在表5.10中。如表所示，和非常接近，当变得相当大，它们也很好的与近似。因此，对于非常大的，例如，使用估计是非常合理的。