algorithm算法原理证明

Floyd’s cycle-finding algorithm

Floyd’s cycle-finding algorithm是一种用于寻找链表中循环或重复元素的算法，也称为Floyd’s tortoise and hare algorithm。该算法使用两个指针，一个称为“乌龟”（tortoise）指针，另一个称为“兔子”（hare）指针。

算法的基本思路是，用两个指针同时从链表的头部出发，乌龟指针每次前进一步，兔子指针每次前进两步。如果链表中不存在循环，那么兔子指针最终会走到链表的末尾，此时算法结束。但是，如果链表中存在循环，那么兔子指针最终会进入循环中，此时兔子指针和乌龟指针必定会相遇。

当兔子指针进入循环后，它会一直绕圈，直到乌龟指针进入循环，兔子指针追上乌龟指针，也就是说，乌龟指针和兔子指针都在循环内部移动。此时，将兔子指针重新置为链表头部，再以每次前进一步的速度移动两个指针，最终它们会在循环的入口处相遇。这是因为兔子指针在每一轮循环中都比乌龟指针多走一圈，所以它们最终相遇的地方就是循环的入口。

该算法的时间复杂度为O(n)，空间复杂度为O(1)，其中n是链表中元素的个数。由于该算法只需要遍历链表一次，因此效率较高，被广泛应用于链表中循环或重复元素的查找。

证明过程

在使用 Floyd’s cycle-finding algorithm 检测一个数是否是合数时，如果这个数有一个非平凡因子，那么它就是合数。这是因为当一个合数 n 有一个非平凡因子 d 时，可以将 n 表示为 n=d * q 的形式，其中 q 是另一个整数。那么 n 的一个非平凡因子就是 d 或 q。如果 d=q，则 d 就是 n 的平方根，因此在检查素性时只需要检查 n 的平方根以下的整数即可。但是如果
$$\begin{array}{}\text{(1)}& d\ne q\end{array}$$
那么我们可以在 Floyd’s cycle-finding algorithm 中找到一个循环，其中循环长度为偶数，这样就找到了一个非平凡的因子。

具体来说，设 f(x) 表示对 n 取模的一个函数，定义为
$$\begin{array}{}\text{(2)}& f(x)=(x^2+1)modn\end{array}$$
从一个初始值开始，可以构造一个序列
$$\begin{array}{}\text{(3)}& x_0,x_1,x_2,\dots \end{array}$$
其中
$$\begin{array}{}\text{(4)}& x_{i+1}=f(x_i)\end{array}$$
x取值范围是
$$\begin{array}{}\text{(5)}& 0\le x_i<n\end{array}$$
因此这个序列必然存在一个循环，即存在
$$\begin{array}{}\text{(6)}& i<j\mathrm{而}\mathrm{且}{x}_i=x_j\end{array}$$
假设循环长度为偶数，即存在一个正整数 k，使得
$$\begin{array}{}\text{(7)}& x_i=x_{i+k}\mathrm{且}{x}_{i+1}=x_{i+k+1}\end{array}$$
那么可以证明
$$\begin{array}{}\text{(8)}& d=gcd(x_i-x_{i+k},n)\mathrm{是}n\mathrm{的}\mathrm{非}\mathrm{平}\mathrm{凡}\mathrm{因}\mathrm{子}\end{array}$$
证明如下：根据假设，有
$$\begin{array}{}\text{(9)}& x_i=x_{i+k}\mathrm{和}{x}_{i+1}=x_{i+k+1}\mathrm{存}\mathrm{在}(x_{i+1}-x_i)=(x_{i+k+1}-x_{i+k})(\mathrm{mod}n)\end{array}$$
那么，即
$$\begin{array}{}\text{(10)}& (x_{i+1}-x_i)\equiv (x_{i+k+1}-x_{i+k})(\mathrm{mod}n)\end{array}$$
由于
$$\begin{array}{}\text{(11)}& f(x)=(x^2+1)modn\end{array}$$
因此有
$$\begin{array}{}\text{(12)}& x_{i+1}\equiv x_i^2+1(\mathrm{mod}n)\end{array}$$

$$\begin{array}{}\text{(13)}& x_{i+k+1}\equiv x_{i+k}^2+1(\mathrm{mod}n)\end{array}$$

代入上式得到
$$\begin{array}{}\text{(14)}& x_i^2-x_{i+k}^2\equiv x_{i+1}-x_{i+k+1}(\mathrm{mod}n)\end{array}$$
即
$$\begin{array}{}\text{(15)}& (x_i-x_{i+k})(x_{i+1}+x_{i+k+1}-1)\equiv 0(\mathrm{mod}n)\end{array}$$

$$\begin{array}{}\text{(16)}& x_i=x_{i+k}，\mathrm{那}\mathrm{么}d=gcd(x_i-x_{i+k},n)=gcd(0,n)=n\end{array}$$

因此，如果我们能够找到一个长度为偶数的环，则可以使用上述方法得到一个非平凡的因子
$$\begin{array}{}\text{(17)}& p=gcd(2^k-1,n)\end{array}$$
假设快指针和慢指针在节点 j 处相遇，此时快指针已经绕了 k 圈了，那么有：
$$\begin{array}{}\text{(18)}& k=\frac{2\cdot \mathrm{环}\mathrm{的}\mathrm{长}\mathrm{度}}{\mathrm{慢}\mathrm{指}\mathrm{针}\mathrm{进}\mathrm{入}\mathrm{环}\mathrm{之}\mathrm{前}\mathrm{走}\mathrm{过}\mathrm{的}\mathrm{距}\mathrm{离}-\mathrm{快}\mathrm{指}\mathrm{针}\mathrm{进}\mathrm{入}\mathrm{环}\mathrm{之}\mathrm{前}\mathrm{走}\mathrm{过}\mathrm{的}\mathrm{距}\mathrm{离}}\end{array}$$
由于慢指针走过的距离是快指针的一半，即
$$\begin{array}{}\text{(19)}& \mathrm{慢}\mathrm{指}\mathrm{针}\mathrm{进}\mathrm{入}\mathrm{环}\mathrm{之}\mathrm{前}\mathrm{走}\mathrm{过}\mathrm{的}\mathrm{距}\mathrm{离}=\frac{\mathrm{环}\mathrm{的}\mathrm{长}\mathrm{度}}{2}\end{array}$$
因此上式可以进一步化简为：
$$\begin{array}{}\text{(20)}& k=\frac{\mathrm{环}\mathrm{的}\mathrm{长}\mathrm{度}}{\mathrm{快}\mathrm{指}\mathrm{针}\mathrm{进}\mathrm{入}\mathrm{环}\mathrm{之}\mathrm{前}\mathrm{走}\mathrm{过}\mathrm{的}\mathrm{距}\mathrm{离}-\frac{\mathrm{环}\mathrm{的}\mathrm{长}\mathrm{度}}{2}}\end{array}$$
因为快指针每次走两步，所以 快指针进入环之前走过的距离 是 环的长度的整数倍，即
$$\begin{array}{}\text{(21)}& \mathrm{快}\mathrm{指}\mathrm{针}\mathrm{进}\mathrm{入}\mathrm{环}\mathrm{之}\mathrm{前}\mathrm{走}\mathrm{过}\mathrm{的}\mathrm{距}\mathrm{离}=x\ast \mathrm{环}\mathrm{的}\mathrm{长}\mathrm{度}\end{array}$$
代入上式中得：
$$\begin{array}{}\text{(22)}& k=\frac{2}{x-1}\end{array}$$
因为 k 是整数，所以 x-1 必须是 2 的因子。根据前面的推导，环的长度是偶数，因此 x-1 必须是一个非平凡的因子，即 x-1 不等于 1和 n。因此我们可以通过找到一个非平凡的因子来判断 n 是否是合数。