TIME: 1:30-2:20 pm, May 2, 2006 PLACE: CSE 403 TITLE: Spectra analysis of Pollard Rho Collisions SPEAKER: Ramarathnam Venkatesan Microsoft Research ABSTRACT: We show that the classical Pollard Rho algorithm for discrete logarithms produces a collision in expected time O(\sqrt{n}(log n)^3). This is the first nontrivial rigorous estimate for the collision probability for the unaltered Pollard Rho graph, and is close to the conjectured optimal bound of O(sqrt{n}). The result is derived by showing that the mixing time for the random walk on this graph is O((log n)^3); without the squaring step in the Pollard Rho algorithm, the mixing time would be exponential in log n. The technique involves a spectral analysis of directed graphs, which captures the effect of the squaring step. The graph's generalizations are suitable for stream cipher for constructions and in fact our analysis originated there. A mini survey of discrete log, cayley/expander graphs, and characters on abelian groups will be included. Joint work with Stephen Miller. Paper at http://www.math.rutgers.edu/~sdmiller/