Choosing iteration maps for the parallel Pollard rho method

Finn Rudolph · 2025

Read Choosing iteration maps for the parallel Pollard rho method by Finn Rudolph (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12844.txt.

Introduction

Finn Rudolph studies iteration maps for the parallel Pollard rho method, a classic way to find a prime factor of a large integer, in a solo work from 2025. The method searches for a collision in a repeated map. Several machines can search at once with distinct settings. Rudolph gives an asymptotic estimate for the expected running time, based on each machine's choice. He also proves the simplest setting is best for one machine when nothing is known in advance.

Catalog record

CREATORFinn Rudolph
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-12844

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Choosing iteration maps for the parallel Pollard rho method Finn Rudolph Abstract . Pollard’s rho method finds a prime factor p p of an integer N N by searching for a collision in a map of the form x ↦ x 2 ​ k + c x\mapsto x^{2k}+c modulo N N . This search can be parallelized to multiple machines, which may use distinct parameters k k and c 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 k for each machine. We also prove that k = 1 k=1 is the best choice for one machine, if nothing about p p is known in advance. 2020 Mathematics Subject Classification 11Y05, 11Y16, 68W10 1. Introduction In [ CP05 , p. 255,5.24] , Crandall and Pomerance pose the following question: Assume M machines run the rho method independently on an integer N and the i -th machine uses x\mapsto x^{2k_{i}}+c_{i} as its iteration map. How to assign parameters k_{i} to them in an optimal way? This problem is the subject of this paper. Let N\in\mathbb{N}_{\geq 2} be the number to be factored and p be the smallest prime divisor of N not equal to 2. Statements about the expected running time of the rho method to factor N are always made in terms of p . The choice of the c_{i} is not discussed here, since they do not seem to have much influence on the running time and are best chosen independently at random. (Except that 0 and -2 should be avoided, see [ Pol75 , p. 333] and [ Cra99 , p. 6] .) In contrast, the k_{i} can affect the running time significantly depending on their common factors with p-1 . Let d_{i}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\gcd(p-1,2k_{i}) . The expected number of steps the i -th machine requires is reduced by a factor of \sqrt{d_{i}-1} (this will become clear from Theorem 1 , or see [ BP81 ] ). However, the running time per iteration of the i -th machine is increased by a factor of \log_{2}2k_{i} in comparison to k_{i}=1 . Thus, it is not immediately clear which choice of k_{i} yields the best expected running time. 1.1. The main result As usual for the analysis of the rho method, we assume that the rho iteration map behaves like a random map (see Heuristic 1 ). Under this assumption, the expected time until some machine finds p as a factor of N is asymptotic to (1.1) \displaystyle\sqrt{\pi p/2}\,\left\lparen\sum_{i=1}^{M}\frac{\gcd(p-1,2k_{i})-1}{\log_{2}^{2}2k_{i}}\right\rparen^{\!\!-1/2} as p\to\infty . We say two functions f,g:(0,\infty)\to(0,\infty) are asymptotic and write f\sim g , if \lim_{x\to\infty}f(x)/g(x)=1 . For M=k_{1}=1 , ( 1.1 ) evaluates to \sqrt{\pi p/2} , which is the classical estimate for rho method given by [ Pol75 ] . For M=1 and arbitrary k_{1} , ( 1.1 ) reduces to \displaystyle\sqrt{\pi p/2}\;\frac{\log_{2}2k_{1}}{\sqrt{\gcd(p-1,2k_{1})-1}}\,. This also matches previous results, see e.g. [ BP81 ] or [ CP05 , p. 255,5.24] . 1.2. Formulation for random maps We briefly recall aspects of the rho method relevant to our analysis. For a complete description of the algorithm, see [ Pol75 ] or [ CP05 , p. 229] . As mentioned in § 1.1 , there is a commonly used heuristic for analyzing the rho method. To state it, a few definitions are required. Let \displaystyle f_{i}:\mathbb{Z}/p\mathbb{Z}\to\mathbb{Z}/p\mathbb{Z},\quad f_{i}:x\mapsto x^{2k_{i}}+c_{i} be the iteration map of the i -th machine, viewed modulo p , and x_{i,0}\in\mathbb{Z}/p\mathbb{Z} its initial value, also modulo p . The initial value is chosen uniformly at random from \mathbb{Z}/N\mathbb{Z} . Let f:X\to X be a function on a finite set X and denote by f^{j} the j -fold composition of f with itself. For an element x\in X , we define the rho length of f at x by \displaystyle\rho(f,x)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left\lvert\left\{f^{j}(x):j\in\mathbb{N}\right\}\right\rvert. We include 0 in the natural numbers, so x is also in the above set. Let n,d\in\mathbb{N}_{\geq 1} and assume that d divides n . Define \mathcal{F}_{n}^{d} as the set of all functions f:\mathbb{Z}/n\mathbb{Z}\to\mathbb{Z}/n\mathbb{Z} such that |f^{-1}\{x\}|\in\{0,d\} for every x\in\mathbb{Z}/n\mathbb{Z} . When picturing an element of \mathcal{F}_{n}^{d} as a directed graph, exactly n/d nodes have indegree d , and all other nodes have indegree 0. The main issue in the analysis of the rho method is to estimate the number of iterations a machine requires to discover p . This number is \rho(f_{i},x_{i,0}) for the the i -th machine, since it iterates f_{i} starting from x_{i,0} until a value is encountered twice. However, there are currently no estimates for the distribution or mean of \rho(f_{i},\,\cdot\,) known, so we rely on the following heuristic. Heuristic 1 . The distribution of \rho(f_{i},\,\cdot\,) is close to the distribution of the map \mathcal{F}_{p-1}^{d_{i}}\times\mathbb{Z}/(p-1)\mathbb{Z}\to\mathbb{N} sending (f,x) to \rho(f,x) . Close is to be understood as close enough to be interchangeable for the analysis of the rho method. An intuitive justification for Heuristic 1 stems from the distribution of indegrees of f_{i} . Let (\mathbb{Z}/p\mathbb{Z})^{\times} be the group of units of \mathbb{Z}/p\mathbb{Z} . Since (\mathbb{Z}/p\mathbb{Z})^{\times} is cyclic, exactly (p-1)/d_{i} elements have d_{i} preimages under the map x\mapsto x^{2k_{i}} on (\mathbb{Z}/p\mathbb{Z})^{\times} . So the distribution of indegrees of f_{i} equals the distribution of indegrees of elements in \mathcal{F}_{p-1}^{d_{i}} , up to a shift by one due to the inclusion of zero. Thus, heuristically assuming that f_{i} exhibits no further patterns, we approximate the distribution of \rho(f_{i},\,\cdot\,) by the rho length distribution of a random element of \mathcal{F}_{p-1}^{d_{i}} . Crude as this heuristic may seem, it works remarkably well in practice. Theoretical and numerical results regarding Heuristic 1 are summarized in § 7.3 . We now formulate a rigorous result that can be used to derive ( 1.1 ) under Heuristic 1 . Let n\in\mathbb{N}_{\geq 1} and d_{i}\in\mathbb{N}_{\geq 1} such that d_{i}\mid n for every 1\leq i\leq M . We consider M machines simultaneously iterating a function on \mathbb{Z}/n\mathbb{Z} . Each machine stops when it encounters a repeated value. The function used by the i -th machine is drawn uniformly at random from \mathcal{F}_{n}^{d_{i}} and its initial value is drawn uniformly from \mathbb{Z}/n\mathbb{Z} . The setup is represented by the space \Omega\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\prod_{i=1}^{M}\left\lparen\mathbb{Z}/n\mathbb{Z}\times\mathcal{F}_{n}^{d_{i}}\right\rparen , equipped with the uniform probability measure. Theorem 1 . For 1\leq i\leq M , let \lambda_{i}\in(0,\infty) and define random variables X_{i}:\Omega\to\mathbb{R} by X_{i}((x_{1},g_{1}),\dots,(x_{M},g_{M}))=\lambda_{i}\rho(g_{i},x_{i}) . Then (1.2) \displaystyle\mathbb{E}\left\lparen\min_{i=1}^{M}X_{i}\right\rparen\sim\sqrt{\pi n/2}\left\lparen\sum_{i=1}^{M}\frac{d_{i}-1}{\lambda_{i}^{2}}\right\rparen^{\!\!-1/2} as n\to\infty . One may interpret \lambda_{i} as the time per iteration of the i -th machine, and X_{i} as the time required by the i -th machine to terminate. Formula ( 1.1 ) follows from Theorem 1 by taking n=p-1 , d_{i}=\gcd(p-1,2k_{i}) and \lambda_{i}=\log_{2}2k_{i} . We choose \lambda_{i}=\log_{2}2k_{i} , because calculating the power x^{2k_{i}} in each iteration requires \log_{2}2k_{i} steps (see § 7.2 for more details). 1.3. Without information about p To apply ( 1.1 ), we need to know \gcd(p-1,2k_{i}) for every 1\leq i\leq M . But often such information is not available when trying to factor a large number. This raises a natural question: Which k_{i} should be chosen if nothing about p is known? To address this question, we consider all possible congruences of p modulo \ell\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\lcm\{2k_{i}:1\leq i\leq M\} , since we already know the expected running time for a fixed congruence class from ( 1.1 ). Since

Read the complete text