Abstract
We formally show that there is an algorithm for DLOG over all abelian groups that
runs in expected optimal time (up to logarithmic factors) and uses only a small
amount of space. To our knowledge, this is the first such analysis. Our
algorithm is a modification of the classic Pollard rho, introducing explicit
randomization of the parameters for the updating steps of the algorithm, and is
analyzed using random walks with limited independence over abelian groups (a
study which is of its own interest). Our analysis shows that finding cycles in
such large graphs over groups that can be efficiently locally navigated is as
hard as DLOG.
Reference
Jeremy Horwitz
and Ramarathnam
Venkatesan, "Random Cayley Digraphs and the Discrete
Logarithm", Algorithmic Number Theory Symposium V, ANTS-V
(LNCS 2369), pp. 100-114, 2002.
Copies of the paper
PostScript
PDF
gzipped PostScript
Return to ...
my home
page my publications
Department of Mathematics and Computer Science
Santa Clara University
Jeremy Horwitz
Last modified: Mon Dec 27 20:47:44 PST 2004