算法分析导论（第2版）

整数因子分解与映射 在这一节，我们将考查波拉德(Pollard)的[插图]算法，这是一个有效的整数（在10到30个十进制位这样的“中等”规模内）因子分解算法，该方法依赖于映射的结构性质及其概率性质。它以如下两个事实为基础。 · 某个环上的一个点可以被快速地找到（所用的时间与一个起始点的[插图]长成比例），所以使用O(1)的内存。 · 随机映射上的一个随机点，其平均[插图]长为[插图]。 首先，我们考虑环的检测问题，然后再来考查波拉德的[插图]算法本身。 环检测 欲找到映射的一个环上的一点，一个朴素的方法就是对映射进行迭代，存储查找结构中所有函数的值，查找每个新值，从而确定某个值是否在结构中再次被取到。这个算法对大的映射并不实用，因为我们无法承担存储所有函数值的空间开销。 程序9.3给出了一个在任意映射中求环上点的方法，该方法只耗用了常数量级的空间而且不牺牲执行时间，它是由Floyd给出的。在这个程序中，我们可以把点a看成正在以速度1沿着[插图]-图运动（见图9.10），把点b看成正在以速度2沿着[插图]-图运动。该算法依赖于这样的事实：一旦这两个点都在环上时，它们必然会在某个位置上相撞。例如，假设该算法被用于图9.10中的映射且起始点为10，则在7步之内，环就会被检测出来，这可以通过跟踪a和b的取值看出。 [插图] 程序9.3 环检测的Floyd算法 [插图] 定理9.11（环检测）　给定一个映射和一个起始点x，Floyd算法使用常数级空间，并在与x的[插图]长成比例的时间内找到映射中一个环上的点。 证明：设[插图]是x的尾长，[插图]为环长，[插图]为[插图]长。经过[插图]步循环之后，点a到达了环，而点b已经在环上。现在环上有一场赛跑，其速度差为1。最多经过[插图]步，b将赶上a。 设t为当算法结束时变量t[插图]的值，则我们也必有 [插图] 左端的不等式成立，是因为t是点a的位置，且算法在a第二次开始绕环运动之前就应结束。右端的不等式成立，是因为2t是点b的位置，且算法应在b至少绕行一周之后才能结束。因此，这个算法不仅给出了环上的一个位置（变量a和b结束时的值），也给出了起始点的[插图]长的一个估计，且估计的值被一个因子2给出的范围所限定。 通过再多存储一些函数值，差不多消去算法所花费的时间中额外的因子2（以及估计[插图]长时的不确定性）是可能的，而所用的存储空间的量仍然比较合理。Sedgewick等对这一问题进行了详细的研究。 习题9.61　利用Floyd方法在你的机器上对较短的环检验随机数生成器。 习题9.62　利用Floyd算法检验平方取中法随机数生成器。 习题9.63　对于函数[插图]，利用Floyd方法估计其中与各种起始值、c和N等有关的[插图]长。 波拉德的[插图]算法 [插图]算法是一个以高概率对整数进行因子分解的随机算法。程序9.4给出了它的一个实现，但事先声明，它假设将算法应用于很大的整数是可行的。该算法以一个随机选择的c值为基础，然后再从一个随机选择的起点开始迭代二次函数[插图]，直至找到环上的一个点为止。 程序9.4 用于因子分解的波拉德r算法 [插图] 为简单起见，假设[插图]，其中p和q是算法要找的质数。根据中国剩余定理，任何一个整数y模除N，都由y的值模除p和模除q所确定。特别的是，函数f由一对函数 [插图]以及[插图] 所确定。如果把环检测算法运用到[插图]，并从一个初始值x开始，那么经过[插图]步之后将会检测到一个环，其中[插图]至多