Pollard Rho因子分解法

Question

Pollard Rho因式分解法使用函數發生器f（x）= x^2-a（mod n）或f（x）= x^2 + a（mod n）函數（拋物線）具有任何意義，或者我們可以使用任何函數（立方，多項式甚至線性），因爲我們必須識別或找到屬於同一類模n的數以找到非平凡除數？

Answer 1

在Knuth的第II卷（在本領域計算機編程 - 半數值算法）部分4.5.4 Knuth的說

此外如果f（y）的模p表現爲從集合{0， 隨機映射1，... p-1}自身，練習3.1-12表明，平均值 最小的m將是sqrt（p）。從第3章 的理論可知，對於我們的目的，線性多項式f（x）= ax + c不會是足夠隨機的 。下一個最簡單的例子是 二次方程，比如f（x）= x^2 +1。我們不知道知道這個函數是 足夠隨機的，但我們缺乏知識傾向於支持隨機性假設，並且經驗性測試表明，此F確實 工作基本上如預測

概率理論說使f（x）具有長度的約SQRT（p）週期在特定假定可以有兩個值y和z使得f（y）= f（z） - 因爲f是隨機選擇的。 Pollard Rho中的rho包含這樣一個交匯點，其中包含多條線的循環通向它。對於線性函數f（x）= ax + b，那麼對於gcd（a，p）= 1 mod p（這可能是因爲p是質數）f（y）= f（z）意味着y = z mod p，所以沒有這樣的路口。

如果你看看http://www.agner.org/random/theory/chaosran.pdf，你會看到隨機函數的預期週期長度約爲狀態長度的sqrt，但隨機雙向預期週期長度約爲狀態長度。如果您只是在評估時產生隨機函數，則可以看到如果函數完全是隨機的，那麼到目前爲止所看到的每個值都可以隨機再次選擇以找到一個週期，所以關閉週期的機率增加與循環長度一致，但是如果函數必須是可逆的，則關閉循環的唯一方法是生成起始點，該起始點的可能性要小得多。