Collisions and Floyd's Cycle-Finding Algorithm
Collisions and Pollard’s rho
这里主要是介绍 Pollard’s rho 在哈希碰撞上的应用，还有弗洛伊德循环检测算法（Floyd’s Cycle-Finding Algorithm），也称为龟兔赛跑算法（Tortoise and Hare Algorithm）。值得吐槽的是 Antoine 这里就用了七八页，难道法国人都是这么上课的？
1. Pollard’s rho算法的基本原理
生日悖论
生日悖论指出，在一个集合中，如果有23个人，那么至少两个人在同一天生日的概率大于50%。这一悖论表明，在一个相对较小的集合中，随机选择若干次后发生碰撞（即两个不同的选择结果相同）的概率很高。Pollard’s rho算法利用这一原理，在较小的搜索空间内寻找碰撞。
随机游走
Pollard’s rho算法模拟了一个伪随机游走过程，即通过一个伪随机函数不断生成新的点（值）。通过监控这些点，可以找到两个不同的输入产生相同输出的碰撞点。
2. Pollard’s rho算法的整数因子分解应用
算法
- 选择初始值：选择一个初始值$x_0$和一个伪随机函数$f$
- 迭代过程：生成序列 $x_{i+1} = f(x_i) \text{mod} n$，其中 $n$ 是待分解的整数。
- 检测碰撞：使用弗洛伊德循环检测算法（也称为龟兔赛跑算法）来检测循环（碰撞）。即，设置两个指针，一个每次前进一步（慢指针），另一个每次前进两步（快指针）。如果存在循环，这两个指针最终会指向同一个值。
- 计算因子：当检测到碰撞时，计算$\gcd(x_i - x_j, n)$ 其中 $x_i, x_j$ 是碰撞点。如果结果不是1且不是$n$，则找到了一个非平凡因子。
3. 弗洛伊德循环检测算法
弗洛伊德循环检测算法（Floyd’s Cycle-Finding Algorithm），也称为龟兔赛跑算法（Tortoise and Hare Algorithm），是一种用于在伪随机数序列或链表中检测循环的有效算法。该算法由罗伯特·弗洛伊德（Robert W. Floyd）提出。它通过两个指针的步进方式来发现循环，使用了极少的额外空间。
算法原理
弗洛伊德循环检测算法通过两个指针（通常称为“龟”（tortoise）和“兔”（hare））在序列上行进来检测是否存在循环：
龟和兔的初始化：
- 龟（慢指针）从序列的起始位置出发，每次移动一步。
- 兔（快指针）从序列的起始位置出发，每次移动两步。
行进过程：
- 在每一步，龟指针移动一步，而兔指针移动两步。
- 如果存在循环，那么龟和兔指针最终会在循环内部的某一点相遇。
检测循环：
- 如果龟和兔指针在某一步相遇，则说明序列中存在循环。
- 如果兔指针遇到序列的终点（在有限链表中），则说明序列中不存在循环。
算法步骤
假设我们有一个函数 $f$ ，其输入是整数，输出也是整数，并且我们生成一个序列 $x_0, x_1, x_2, \ldots$ 使得 $x_{i+1} = f(x_i)$ 。我们需要检测这个序列中是否存在循环。
- 初始化指针：
- 设定初始值 $x_0$。
- 令龟指针和兔指针都指向初始值 $x_0$。
- 移动指针：
- 龟指针每次移动一步，即 $龟=f(龟)$。
- 兔指针每次移动两步，即 $兔=f(f(兔))$。
- 检测相遇：
- 在每一步，检查龟指针和兔指针是否相遇（即 $龟==兔$）。
- 如果相遇，则存在循环。
- 如果兔指针到达序列的末尾（对于链表表示来说是空指针），则不存在循环。
- 确定循环的起点：
- 一旦检测到循环（即龟和兔相遇），重新将龟指针指向起始位置 $x_0$，并让兔指针保持在相遇点。
- 这次龟和兔指针都每次只移动一步。
- 龟和兔再次相遇的点即为循环的起点。
示例
假设我们有如下链表：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 3 (循环回到3)
初始化：龟和兔都指向1。
第一步：龟指向2，兔指向3。
第二步：龟指向3，兔指向5。
第三步：龟指向4，兔指向3。
第四步：龟指向5，兔指向5（相遇点，存在循环）。
通过这种方式，弗洛伊德循环检测算法能够有效地找到序列中的循环，并确定循环的起点。同样的，我们就可以使用这个算法来实现对哈希进行碰撞。基本的思想就是一个哈希函数$x_{i+1}=H(x_i)$ 这样就可能构成了一个环（存在碰撞），可以用弗洛伊德循环检测算法能够有效地找到序列中的循环，也就找到了一个碰撞。
但是我们也可以发现这样做太耗费存储，我们需要将所有步骤的结果记录下来，这样才能找到碰撞，所以我们需要Time-memory tradeoff，引入Distinguished point technique，显著点来进行计算。
4. 显著点
显著点是指满足特定条件的伪随机序列中的点。通常，这些条件使得显著点相对稀有，一种显著点定义方法是：将一个数的二进制表示中的若干最低位（比如前8位或前16位）设为零。例如，设定一个数的前8位为零作为显著点：
- 设定条件：$x \mod 2^8 = 0$
- 数 $x$ 的最低8位必须全部为零。
引入显著点之后，我们还可以分布式的计算，我们在不同的service上面，选择不同的初始节点，之后每个service上面，计算的时候只关注是否实现了Distinguished point，如果出现了Distinguished point，就记录下来，之后从Distinguished point开始计算链条，这样找到碰撞的概率大一些。而且节省了存储。不需要存储整个链条，并且可以分布式计算。