Accelerating Pollard's Rho Algorithm on Finite Fields

摘要

Most generic and memory-efficient algorithms for solving the discrete logarithm problem construct a certain random graph consisting of group element nodes and return the solution when a collision is found among the graph nodes. In this work, we develop a technique for traveling through the random graph without fully computing each node and also provide an extension to the distinguished point collision detection method that is suitable for this new situation. Concrete constructions of this technique for multiplicative subgroups of the finite fields are given. Our implementations confirm that the proposed technique provides practical speedup over existing algorithms.