Choosing iteration maps for the parallel Pollard rho method

2025/06/15 by Rudolph, Finn
#11Y05 #11Y16 #68W10 #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2506.12844

Abstract

Pollard's rho method finds a prime factor p of an integer N by searching for a collision in a map of the form x ↦ x^2k + c modulo N. 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 is the best choice for one machine, if nothing about p is known in advance.

Citations

• An improved Monte Carlo factorization algorithm
• A monte carlo method for factorization

Related

• A quantum version of Pollard's Rho of which Shor's Algorithm is a particular case
• A distributed prime sieving algorithm based on Scheduling by Multiple Edge Reversal
• An Empirical Comparison of the Quadratic Sieve Factoring Algorithm and the Pollard Rho Factoring Algorithm
• An Asynchronous Parallel Randomized Kaczmarz Algorithm
• A Note on Algorithms for Computing p_n