Toward a theory of Pollard's rho method

DOI10.1016/0890-5401(91)90001-IMaRDI QIDQ752762zbMATH OpenWikidataFDO

Publication date 1991

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(91)90001-I

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Analysis of algorithms and problem complexity (68Q25)

Review text

The author offers a nonheuristic explanation of the remarkable effectiveness of the Pollard rho method of factorization, see [\textit{H. Riesel}, Prime numbers and computer methods for factorization (1985; Zbl 0582.10001)]. If N has a factor p then the factor appears from finding the sequence \[ f_ 0=x,\quad f_{n+1}=f^ 2_ n+y \] and seeing that \(\gcd (f_ i-f_ j,N)\) is p in about \(\sqrt{p}\) iterates. The author factors \(f_ i-f_ j\) and selects special simple factors \(\rho_{i,j}\) monic in y in which to look for p. Indeed these factors, as curves, have a strong tendency to not intersect in \({\mathbb{Q}}\) and thus in \({\mathbb{C}}\). He uses A. Weil's theorem that for a polynomial f(x,y) of degree d, the number of projective zeroes \(N_ p\) in \({\mathbb{F}}_ p\) satisfies \(| N_ p-p-1| <(d-1)(d-2)\sqrt{p}.\) His main results are that for k fixed and \(0\leq x,y<p\) randomly chosen, the probability that \(f_ i-f_ j\equiv 0\) mod p for \(i,j<k(i\neq j)\) is at least \(k(k- 1)/2p+O(1/p^{3/2})\), as \(p\to \infty\). Also if pq\(| N\) for two primes, \(p<q\), then for some \(i<(\log_ 2p)/4\), \(\gcd (f_{2i+1}-f_ i,N)\neq 1\) with probability \(\Omega (\log^ 2p)/p\). The paper is remarkable for its heavy use of algebraic geometry to avoid the usual indulgence in heuristic.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Toward a theory of Pollard's rho method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q752762)