问题及解答

Pollard rho 算法使用函数 $f(x)=x^2+1\pmod N$ 来生成序列.

假设 $x_t\equiv x_{t+\ell}\pmod p$, 其中 $\ell$ 是周期.

取 $i=t+\ell-(t\mod \ell)$, 则 $i=\ell\cdot([\frac{t}{\ell}]+1)$

\[
i=\begin{cases}
\ell\cdot\lceil\frac{t}{\ell}\rceil,&\text{当}\ \ell\mid t\text{时},\\
\ell\cdot([\frac{t}{\ell}]+1), &\text{当}\ \ell\not\mid t\text{时},\\
\end{cases}
\]