pollard-rho 的序列是这样的:
首先有函数(或者叫映射?) f(x)=(x2+c)mod nf(x)=(x^2+c)\mod nf(x)=(x2+c)modn。
整数序列 aaa 满足 a1=x,x∈[3,n)∩Za_1=x,x\in[3,n)\cap Za1=x,x∈[3,n)∩Z,ai+1=f(ai)a_{i+1}=f(a_i)ai+1=f(ai)。
求证:
对于 ∀c∈[3,n),x,n\forall c\in[3,n),x,n∀c∈[3,n),x,n,如果从编号为 aia_iai 的点向编号为 ai+1a_{i+1}ai+1 的点连一条有向边,图中一定有环(即 aaa 存在循环节)。
另外:还有没有类似的函数 fff 也具有如上的性质?如果有,那么为什么 pollard-rho 要选用上面的而不是另外的,是否有些效率上的差别?