同求（
by critnos @ 2020-05-25 20:48:20
我说的是把它假定为随机的很不严格，不是生日悖论本身
by 01190220csl @ 2020-05-25 20:48:22
这个 好像是open problem？
by qwaszx @ 2020-05-25 20:52:18
自己看wiki去啊
> If the pseudorandom number ${\displaystyle x=g(x)}$ occurring in the Pollard ρ algorithm were an actual random number, it would follow that success would be achieved half the time, by the Birthday paradox in ${\displaystyle O({\sqrt {p}})\leq O(n^{1/4})}$ iterations. It is believed that the same analysis applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.
by cosmicAC @ 2020-05-25 21:04:56
Wikipedia 上说了这个是 Open 的。
原话：
https://www.luogu.com.cn/image?_t=1590412052209
by JohnVictor @ 2020-05-25 21:07:59
cosmicAC 说了，我晚了
by JohnVictor @ 2020-05-25 21:08:39
@[01190220csl](/user/61068) 不是那个式子保证混沌性又保证循环吗，所以用生日悖论得到求出任意一个因子p的期望次数是$O(\sqrt{p})$的啊，所以最小的那个p最容易先取到啊
by Haishu @ 2020-05-25 21:42:35
@[Hygebra](/user/34907) 我在问严格证明
因为它只是看起来“随机”
应当避免假定“随机”才算严格
>不是那个式子保证混沌性又保证循环吗
保证混沌性正是需要证明的
只是看起来具有是不严格的
by 01190220csl @ 2020-05-25 21:49:48
@[01190220csl](/user/61068)
我以为你要证pollardrho，谁知道你要证伪随机数的混沌性QwQ
反正和那啥曼德勃罗集有关吧，这个只是找了一个比较好的伪随机数而已，满足比较随机而且知道当前的那么它的下一项确定的这个性质。你换一个有相同性质的随机数也行。
by Haishu @ 2020-05-25 21:53:02
@[01190220csl](/user/61068) 你再找一个状态数只有$O(n)$的伪随机数呗
by 吾乃会虎 @ 2020-05-26 17:10:34