Optimal iteration maps and a rigorous random-map analysis for the parallel Pollard rho method

Pollard's rho method factors an integer $N$ by iterating a map $x \mapsto x^{2k}+c \bmod N$ and detecting a collision modulo the unknown prime factor $p$; its classical expected running time of order $\sqrt{p}$ steps rests on an unproven heuristic that the iteration map behaves like a random function. Rudolph (2025/2026) analyzed the parallel variant, in which $M$ machines iterate maps $x \mapsto x^{2k_i}+c_i$ with possibly distinct $k_i$, and reduced the choice of the exponents $k_i$ to an explicit arithmetic cost function $G(k_1,\dots,k_M)$ obtained by averaging the asymptotic running time over all congruence classes of $p$ modulo $\mathrm{lcm}(2k_1,\dots,2k_M)$. Two questions are left open and are bundled here as the source presents them: (A) for $M \ge 2$, characterize the tuples $(k_1,\dots,k_M)$ that minimize $G$ — the conjectured answer, supported by extensive computation, is $k_1 = \dots = k_M = 1$, and this is proven only for $M = 1$; and (B) derive provable estimates for the distribution or mean of the rho length (the number of iterations from the starting point until a value repeats) of the concrete polynomial maps $x \mapsto x^{2k}+c \bmod p$, or prove sufficient conditions under which the random-map heuristic (Heuristic 1 of the source) is valid, which would place the expected $\sqrt{p}$-time analysis of the parallel rho method on rigorous foundations.

Background

Pollard's rho method (1975) is a classical integer-factorization algorithm: to split $N$, one iterates a map $f(x) = x^{2k} + c$ modulo $N$ (classically $k = 1$) from a random start and looks for two iterates that are congruent modulo some prime $p \mid N$ but not modulo $N$ (detected via greatest common divisors, computed in batches following Brent). Viewing $f$ modulo $p$, the iteration enters a cycle after a tail; the shape resembles the Greek letter rho, and the number of steps until a value repeats is called the rho length. Because a uniformly random function on a set of size $p$ takes about $\sqrt{\pi p/2}$ steps to revisit a value (the birthday paradox), the method is heuristically expected to find $p$ in about $\sqrt{p}$ iterations — but no proof is known that the specific polynomials $x^{2k}+c$ behave like random functions in this respect; this is the decades-old Brent–Pollard random-map heuristic. When $d = \gcd(p-1, 2k) > 1$, the power map $x \mapsto x^{2k}$ is $d$-to-1 on the nonzero residues modulo $p$, which reduces the expected number of steps by a factor of about $\sqrt{d-1}$, while computing $x^{2k}$ by binary exponentiation (repeated squaring) costs about $\log_2(2k)$ multiplications per iteration. Crandall and Pomerance posed the question of how $M$ parallel machines, the $i$-th using $x \mapsto x^{2k_i}+c_i$, should choose the $k_i$. Rudolph (arXiv:2506.12844; journal version in Designs, Codes and Cryptography, 2026) answered this under a formalized random-map assumption: Heuristic 1 assumes that the rho length of the concrete map $x \mapsto x^{2k_i}+c_i$ modulo $p$ is distributed like that of a uniformly random element of the family $\mathcal{F}_{p-1}^{d_i}$ of functions on $\mathbb{Z}/(p-1)\mathbb{Z}$ in which every point has either $0$ or $d_i$ preimages ($d_i = \gcd(p-1, 2k_i)$), mirroring the preimage structure of the power map. Under this heuristic the paper proves a rigorous theorem (its Theorem 1) giving the expected parallel running time asymptotically, and, averaging this cost over all congruence classes of $p$ modulo $\ell = \mathrm{lcm}(2k_1,\dots,2k_M)$ — the classes that occur equally often among primes, by Dirichlet's theorem on primes in arithmetic progressions — defines the explicit cost function $G(k_1,\dots,k_M)$ of its formula (1.3), which is proportional to the expected time when nothing is known about $p$. The paper proves $G(1) < G(k)$ for every $k \ge 2$, i.e., $k = 1$ is optimal for a single machine, and verifies numerically (for $2 \le M \le 10$, with $k_i$ up to 3000 for $M = 2$, using the author's published program) that $k_1 = \dots = k_M = 1$ minimizes $G$. Rigorous results toward the random-map heuristic are only partial: Bach (1991) estimated the success probability after a given number of steps; Bridy and Garton (2018) proved that the cycle structure of unicritical polynomials — those of the form $x^{d}+a$, whose only critical point is $0$ — over finite fields is as random as the algebraic constraints allow, yet provably cannot exactly match that of random maps (the number of cycles of length $m$ is bounded by $\deg(f^{m})/m$, where $f^{m}$ is the $m$-fold iterate of the map $f$); Martins and Panario (2015) surveyed and extended results on the expected rho length of polynomial families over finite fields, where the indegree distribution (the distribution of preimage counts) plays a central role; Mans, Sha, Shparlinski and Sutantyo (2022) determined the number of leaves (points with no preimages) in the functional graphs — the directed graphs of a self-map, each point pointing to its image — of certain quadratic polynomial families. None of these gives distributional or mean estimates for the rho length of the maps $x^{2k}+c$ actually used by the algorithm.

Problem Statement

The source paper poses two linked open questions whose common objective is to place the choice of iteration maps and the expected running time of the parallel Pollard rho method on rigorous foundations.

(A) For every number of machines $M \ge 2$, determine with proof which tuples $(k_1, \dots, k_M)$ of positive integers minimize the cost function $G(k_1, \dots, k_M)$ defined by formula (1.3) of Rudolph (2026):

$$G(k_1,\dots,k_M) = \frac{1}{\varphi(\ell)} \sum_{d \in (\mathbb{Z}/\ell\mathbb{Z})^{\times}} \left( \sum_{i=1}^{M} \frac{\gcd(d-1, 2k_i) - 1}{(\log_2(2k_i))^2} \right)^{-1/2},$$

where $\ell = \mathrm{lcm}(2k_1, \dots, 2k_M)$, $(\mathbb{Z}/\ell\mathbb{Z})^{\times}$ denotes the invertible residue classes modulo $\ell$ (of which there are $\varphi(\ell)$, with $\varphi$ Euler's totient function), and $\log_2$ is the base-2 logarithm; for the all-ones tuple this evaluates to $G(1,\dots,1) = M^{-1/2}$. In particular, prove or refute that $G(1, \dots, 1) \le G(k_1, \dots, k_M)$ for all tuples of positive integers, and determine whether equality can occur only at $k_1 = \dots = k_M = 1$.

(B) For the concrete iteration maps $f(x) = x^{2k} + c$ modulo a prime $p$ (with $k \ge 1$ and constants $c$ chosen as by the algorithm, avoiding the degenerate values $0$ and $-2$), derive provable asymptotic estimates as $p \to \infty$ for the distribution or the mean of the rho length $\rho(f, \cdot)$, where $\rho(f, x) = |\{f^{j}(x) : j \ge 0\}|$ is the number of distinct iterates of $x$ — equivalently, the number of iterations starting from $x$ until a value repeats — or prove sufficient conditions on $(k, c)$ under which Heuristic 1 of the source holds, i.e., under which the concrete maps may be replaced, for the purposes of the running-time analysis, by uniformly random elements of the family of functions on $\mathbb{Z}/(p-1)\mathbb{Z}$ in which every point has either $0$ or $\gcd(p-1, 2k)$ preimages, so that the expected running-time estimate for the (parallel) rho method becomes a theorem for these maps rather than a heuristic.

Components (A) and (B) share one objective; each is independently meaningful.

References

1. Finn Rudolph, "Choosing iteration maps for the parallel Pollard rho method", arXiv:2506.12844 (2025), https://arxiv.org/abs/2506.12844
2. Finn Rudolph, "Choosing iteration maps for the parallel Pollard rho method", Designs, Codes and Cryptography 94(6) (2026), doi:10.1007/s10623-026-01865-3, https://doi.org/10.1007/s10623-026-01865-3
3. J. M. Pollard, "A monte carlo method for factorization", BIT Numerical Mathematics 15(3) (1975), pp. 331–334, doi:10.1007/BF01933667, https://doi.org/10.1007/BF01933667
4. Richard P. Brent, "An improved Monte Carlo factorization algorithm", BIT Numerical Mathematics 20(2) (1980), pp. 176–184, doi:10.1007/BF01933190, https://doi.org/10.1007/BF01933190
5. Richard P. Brent and J. M. Pollard, "Factorization of the eighth Fermat number", Mathematics of Computation 36(154) (1981), pp. 627–630, doi:10.1090/S0025-5718-1981-0606520-5, https://doi.org/10.1090/S0025-5718-1981-0606520-5
6. Eric Bach, "Toward a theory of Pollard's rho method", Information and Computation 90(2) (1991), pp. 139–155, doi:10.1016/0890-5401(91)90001-I, https://doi.org/10.1016/0890-5401(91)90001-I
7. Andrew Bridy and Derek Garton, "The cycle structure of unicritical polynomials", International Mathematics Research Notices 2020(23) (published online 2018), pp. 9120–9147, doi:10.1093/imrn/rny232, https://doi.org/10.1093/imrn/rny232 (preprint arXiv:1801.03215, https://arxiv.org/abs/1801.03215)
8. Rodrigo S. V. Martins and Daniel Panario, "On the Heuristic of Approximating Polynomials over Finite Fields by Random Mappings", arXiv:1505.02983 (2015), https://arxiv.org/abs/1505.02983
9. Bernard Mans, Min Sha, Igor E. Shparlinski, Daniel Sutantyo, "Functional graphs of families of quadratic polynomials", arXiv:2208.01885 (2022), https://arxiv.org/abs/2208.01885
10. Richard Crandall and Carl Pomerance, "Prime Numbers: A Computational Perspective", 2nd ed., Springer, New York (2005; 1st ed. 2001), doi:10.1007/0-387-28979-8, https://doi.org/10.1007/0-387-28979-8