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 的平方根以下的整数即可。但是如果
$$
d\neq q
$$
那么我们可以在 Floyd’s cycle-finding algorithm 中找到一个循环，其中循环长度为偶数，这样就找到了一个非平凡的因子。
具体来说，设 f(x) 表示对 n 取模的一个函数，定义为
$$
f(x)=(x^2+1)\bmod n
$$
从一个初始值开始，可以构造一个序列
$$
x_0,x_1,x_2,\ldots
$$
其中
$$
x_{i+1}=f(x_i)
$$
x取值范围是
$$
0\le x_i<n
$$
因此这个序列必然存在一个循环，即存在
$$
i<j而且x_i=x_j
$$
假设循环长度为偶数，即存在一个正整数 k，使得
$$
x_i=x_{i+k} 且 x_{i+1}=x_{i+k+1}
$$
那么可以证明
$$
d=\gcd(x_{i}-x_{i+k},n)是n的非平凡因子
$$
证明如下：根据假设，有
$$
x_i=x_{i+k} 和 x_{i+1}=x_{i+k+1} 存在 (x_{i+1}-x_i)=(x_{i+k+1}-x_{i+k})\pmod n
$$
那么，即
$$
(x_{i+1}-x_i)\equiv (x_{i+k+1}-x_{i+k})\pmod n
$$
由于
$$
f(x)=(x^2+1)\bmod n
$$
因此有
$$
x_{i+1}\equiv x_i^2+1\pmod n
$$
$$
x_{i+k+1}\equiv x_{i+k}^2+1\pmod n
$$
代入上式得到
$$
x_i^2-x_{i+k}^2\equiv x_{i+1}-x_{i+k+1}\pmod n
$$
即
$$
(x_i-x_{i+k})(x_{i+1}+x_{i+k+1}-1)\equiv 0\pmod n
$$
$$
x_i=x_{i+k}，那么 d=\gcd(x_{i}-x_{i+k},n)=\gcd(0,n)=n
$$
因此，如果我们能够找到一个长度为偶数的环，则可以使用上述方法得到一个非平凡的因子
$$
p = \gcd(2^k - 1, n)
$$
假设快指针和慢指针在节点 j 处相遇，此时快指针已经绕了 k 圈了，那么有：
$$
k=\frac{2⋅环的长度}{慢指针进入环之前走过的距离−快指针进入环之前走过的距离}
$$
由于慢指针走过的距离是快指针的一半，即
$$
慢指针进入环之前走过的距离=\frac{环的长度}{2}
$$
因此上式可以进一步化简为：
$$
k=\frac{环的长度}{快指针进入环之前走过的距离−\frac{环的长度}{2}}
$$
因为快指针每次走两步，所以 快指针进入环之前走过的距离 是 环的长度的整数倍，即
$$
快指针进入环之前走过的距离=x*环的长度
$$
代入上式中得：
$$
k=\frac{2}{x-1}
$$
因为 k 是整数，所以 x-1 必须是 2 的因子。根据前面的推导，环的长度是偶数，因此 x-1 必须是一个非平凡的因子，即 x-1 不等于 1和 n。因此我们可以通过找到一个非平凡的因子来判断 n 是否是合数。