pollard-rho 的序列问题求助(其实是数学问题)
查看原帖
pollard-rho 的序列问题求助(其实是数学问题)
865625
KobeBeanBryantCox楼主2025/2/1 19:16

pollard-rho 的序列是这样的:

首先有函数(或者叫映射?) f(x)=(x2+c)modnf(x)=(x^2+c)\mod n

整数序列 aa 满足 a1=x,x[3,n)Za_1=x,x\in[3,n)\cap Zai+1=f(ai)a_{i+1}=f(a_i)

求证:

对于 c[3,n),x,n\forall c\in[3,n),x,n,如果从编号为 aia_i 的点向编号为 ai+1a_{i+1} 的点连一条有向边,图中一定有环(即 aa 存在循环节)。

另外:还有没有类似的函数 ff 也具有如上的性质?如果有,那么为什么 pollard-rho 要选用上面的而不是另外的,是否有些效率上的差别?

2025/2/1 19:16
加载中...