算法分析導論（第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開始，那麼經過[插圖]步之後將會檢測到一個環，其中[插圖]至多