Abstract:
Pollard's ρ-algorithm is a factorization method inspired by probabilistic ideas. Its running time is proportional to the ρ-length of the functional graph of a polynomial mod p, where N=pq is the number to factorize. The functional graph of f:V → V is a directed graph with vertex set V and edge set {(x,f(x)): x ∈ V}, whereas the ρ-length of a vertex v is the length of the shortest self-intersecting path starting at v.
In order to study the running time of his algorithm, Pollard made the (rather unrealistic) assumption that a polynomial mod p behaves like a uniform random mapping. In this talk we discuss a different probabilistic model for functional graphs based on fixing the indegree sequence in advance.
Such a model was already suggested by Martins and Panario, who studied the asymptotic behaviour of degree sequences in polynomials mod p.
We show that the rescaled ρ-length in this model converges weakly to a Rayleigh distribution, provided some regularity conditions for the degree sequence hold. The scaling supports the conjecture that the 'typical' running time of Pollard's ρ-algorithm is of order O(N^(1/4).