假设我们要分解的是合数 n,我们生成一个随机函数 f(x)=x2+c(modn),并保证 c=0,2。众所周知 n 存在一个不超过 n 的质因子 p,有一种龟兔赛跑的判环算法,即令 x0=y0=0,然后每次迭代求出 xi−1,y2i−1,并求 gcd(n,∣xi−1,y2i−1∣) 直到 >1 为止退出;或当 xi=y2i−1(modn) 时退出。设 modp 意义下环长为 m,我们相当于对于所有距离 d∈[1,m−1] 都检查了其中的一对 x,y。
这里有个问题:有没有可能在这个 ρ 形上确实存在两个数 x,y 满足 x=y(modn) 且 gcd(∣x−y∣,n)>1,但是我们并没有检查到它们?比如说环上距离为 4 的点确实 modp 意义下是相同的,但是我们检查距离为 4 的点对的时候,还没有上环,停留在 ρ 形的下半部分,导致我们并没有检查到它们。
这种情况是否确实会存在,还是我哪里想错了?如果会存在的话,如何分析其对算法复杂度的影响?
感激不尽!