Toward a theory of Pollard's rho method
type: Item
instance of: scholarly article
title: Toward a theory of Pollard's rho method
zbMATH Open document ID: 0716.11065
DOI: 10.1016/0890-5401(91)90001-I
author: Eric Bach
published in: Information and Computation
publication date: 1991-01-01T00:00:00Z
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.
reviewed by: Harvey Cohn
Mathematics Subject Classification ID: 11Y05
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4179491
zbMATH Keywords: Pollard rho method of factorization
Wikidata QID: Q29031634
MaRDI profile type: Publication
cites work: Random mappings with constraints on coalescence and number of origins
cites work: An improved Monte Carlo factorization algorithm
cites work: Factorization of the Eighth Fermat Number
cites work: Q3715247
cites work: Q5538132
cites work: The Distribution of Absolutely Irreducible Polynomials in Several Indeterminates
cites work: Q3027108
cites work: Q5571530
cites work: Modifikationen des Pollard-Algorithmus
cites work: Q4105720
cites work: Q4143433
cites work: Speeding the Pollard and Elliptic Curve Methods of Factorization
cites work: A monte carlo method for factorization
cites work: Q5511421
cites work: Q3249822
Recommended article: Factorization of the Eighth Fermat Number
Recommended article: Factoring polynomials using fewer random bits
Recommended article: Q3932864
Recommended article: Q2739443
Recommended article: Q3801677
Recommended article: A generalisation of the Cantor-Zassenhaus algorithm
Recommended article: Q3345783
Recommended article: The Probability That a Randomly Generated Quadratic Is Factorable
Recommended article: Modifikationen des Pollard-Algorithmus
description: scientific article; zbMATH DE number 4179491