萌新妹子求助关于 Pollard-Rho 算法
  • 板块学术版
  • 楼主蒟蒻君HJT泽渡透香
  • 当前回复15
  • 已保存回复15
  • 发布时间2023/12/27 18:58
  • 上次更新2023/12/27 21:37:05
查看原帖
萌新妹子求助关于 Pollard-Rho 算法
131591
蒟蒻君HJT泽渡透香楼主2023/12/27 18:58

假设我们要分解的是合数 nn,我们生成一个随机函数 f(x)=x2+c(modn)f(x)=x^2+c \pmod n,并保证 c≠0,2c\neq 0,2。众所周知 nn 存在一个不超过 n\sqrt n 的质因子 pp,有一种龟兔赛跑的判环算法,即令 x0=y0=0x_0=y_0=0,然后每次迭代求出 xi−1,y2i−1x_{i-1},y_{2i-1},并求 gcd⁡(n,∣xi−1,y2i−1∣)\gcd(n,|x_{i-1},y_{2i-1}|) 直到 >1>1 为止退出;或当 xi=y2i−1(modn)x_i=y_{2i-1}\pmod n 时退出。设 mod  p\mod p 意义下环长为 mm,我们相当于对于所有距离 d∈[1,m−1]d\in[1,m-1] 都检查了其中的一对 x,yx,y。

这里有个问题:有没有可能在这个 ρ\rho 形上确实存在两个数 x,yx,y 满足 x≠y(modn)x\neq y\pmod n 且 gcd⁡(∣x−y∣,n)>1\gcd(|x-y|,n)>1,但是我们并没有检查到它们?比如说环上距离为 44 的点确实 mod  p\mod p 意义下是相同的,但是我们检查距离为 44 的点对的时候,还没有上环,停留在 ρ\rho 形的下半部分,导致我们并没有检查到它们。

这种情况是否确实会存在,还是我哪里想错了?如果会存在的话,如何分析其对算法复杂度的影响?

感激不尽!

2023/12/27 18:58
加载中...