Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. On the Use of the Negation Map in the Pollard Rho Method
 
conference paper

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

Bos, Joppe Willem
•
Kleinjung, Thorsten  
•
Lenstra, Arjen K.  
2010
Algorithmic Number Theory
9th International Symposium on Algorithmic Number Theory

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.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

NPDF-45.pdf

Access type

openaccess

Size

258.31 KB

Format

Adobe PDF

Checksum (MD5)

c54c66e3c0e70170fd29c3a830463314

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés