algorithm - Pollard Rho 分解方法

Question

Pollard Rho 分解方法使用函数生成器 f(x) = x^2-a(mod n) 或 f(x) = x^2+a(mod n) ，这个函数的选择（抛物线）有没有意义，或者我们可以使用任何函数（三次、多项式甚至线性），因为我们必须识别或找到属于相同同余类模n的数字才能找到非平凡除数？

Answer 1

在 Knuth Vol II (The Art Of Computer Programming - Seminumerical Algorithms) 第 4.5.4 节 Knuth 说

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