Skip navigation

A limit theorem for the ρ-length of random functional graphs with fixed degree sequences

Stochastik-Kolloquium Frankfurt

Date: 24.04.2018

Time: 14:00 h

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).   

Number

66

Speaker

Dr. Kevin Leckey, TU Dortmund

Place

Goethe-Universität Frankfurt, Raum 711 (groß)
Institut für Mathematik, Robert-Mayer-Str. 10, 60486 Frankfurt

Campus Bockenheim, Robert-Mayer-Str. 10, Raum 711 (groß), 7. Stock

Google Maps


Organizing partners

Technische Universität Darmstadt, Johannes Gutenberg-Universität Mainz

For this event, no registration is necessary. PDF- Link