Choosing iteration maps for the parallel Pollard rho method

Pollard’s rho method finds a prime factor p of an integer \(N\) $N$ by iterating a map of the form \(x \mapsto x^{2k} + c \ (\bmod \, N)\) $x\mapsto x^{2k}+c(modN)$ and detecting a collision modulo p. This search can be parallelized to multiple machines, which may use distinct parameters k and c. In this paper, we give an asymptotic estimate for the expected running time of the parallel rho method depending on the choice of k for each machine. We also prove that \(k = 1\) $k=1$ is the best choice for one machine, if nothing about p is known in advance.