朴素 Pollard Rho 的正确性好像有问题

P4718 【模板】Pollard-Rho

你猜为啥要特判 $N=4$。
by fjy666 @ 2023-07-12 11:08:24


@[0xyz](/user/891963) n=4 好像要判掉()
by QAQ__ @ 2023-07-12 11:11:16


我之前也被这个东西卡住(
by QAQ__ @ 2023-07-12 11:11:36


谢谢,但是为什么只要特判 $N=4$?
by 0xyz @ 2023-07-12 11:15:25


这不叫 Pollard Rho 的正确性有问题,而是构造的函数有问题,采用 $f(x)= (x^2+x+c) \mod{n}\ ,c=1$ 就没问题了。
by kevinzheng0426 @ 2023-10-27 11:10:51


|