On the Use of the Negation Map in the Pollard Rho Method

• Presented at: 9th International Symposium on Algorithmic Number Theory, Nancy, FRANCE, Jul 19-23, 2010
• Published in: Algorithmic Number Theory, p. 66-82
• Series: Lecture Notes in Computer Science 6197
• Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa, 2010

The negation map can be used to speed up the Pollard rho method to compute discrete logarithms in groups of elliptic curves over finite fields. It is well known that the random walks used by Pollard rho when combined with the negation map get trapped in fruitless cycles. We show that previously published approaches to deal with this problem are plagued by recurring cycles, and we propose effective alternative countermeasures. As a result, fruitless cycles can be resolved, but the best speedup we managed to achieve is by a factor of only 1.29. Although this is less than the speedup factor of root 2 generally reported in the literature, it is supported by practical evidence.

Keywords: Pollard's rho method ; fruitless cycles ; negation map ; Elliptic Curve Cryptosystems ; Factorization ; Computation ; Search

Reference

• EPFL-CONF-164553
• doi:10.1007/978-3-642-14518-6_9
• View record in Web of Science

Record created on 2011-03-29, modified on 2017-05-12