Advertisement
Published in:
2010 | OriginalPaper | Chapter
On the Use of the Negation Map in the Pollard Rho Method
Authors : Joppe W. Bos, Thorsten Kleinjung, Arjen K. Lenstra
Published in: Algorithmic Number Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
$\sqrt 2$
generally reported in the literature, it is supported by practical evidence.