algorithm - Pollard Rho 分解方法

Question

Pollard Rho factorization method uses a function generator f(x) = x^2-a(mod n) or f(x) = x^2+a(mod n) ,是这个函数的选择(抛物线)有任何意义，或者我们可以使用任何函数(三次函数、多项式函数甚至线性函数)，因为我们必须识别或找到属于同余类模 n 的数字以找到非平凡除数？

Answer 1

在 Knuth 第 II 卷(计算机编程艺术 - 半数值算法)第 4.5.4 节 Knuth 说

Furthermore if f(y) mod p behaves as a random mapping from the set {0, 1, ... p-1} into itself, exercise 3.1-12 shows that the average value of the least such m will be of order sqrt(p)... From the theory in Chapter 3, we know that a linear polynomial f(x) = ax + c will not be sufficiently random for our purpose. The next simplest case is quadratic, say f(x) = x^2 + 1. We don't know that this function is sufficiently random, but our lack of knowledge tends to support the hypothesis of randomness, and empirical tests show that this f does work essentially as predicted

表示 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您会看到随机函数的预期循环长度大约是状态大小的平方，但随机双射的预期循环长度大约是状态大小。如果您只考虑在评估时生成随机函数，您会发现如果该函数完全随机，那么到目前为止看到的每个值都可以再次随机选择以找到一个循环，因此关闭循环的几率增加与循环长度有关，但如果函数必须是可逆的，则关闭循环的唯一方法是生成起点，这不太可能。