Combining Montgomery Multiplication with Tag Tracing for the Pollard's Rho Algorithm in Prime Order Fields

Madhurima Mukhopadhyay; Palash Sarkar

Paper 2021/043

Combining Montgomery Multiplication with Tag Tracing for the Pollard's Rho Algorithm in Prime Order Fields

Madhurima Mukhopadhyay and Palash Sarkar

Abstract

In this paper, we show how to apply Montgomery multiplication to the tag tracing variant of the Pollard's rho algorithm applied to prime order fields. This combines the advantages of tag tracing with those of Montgomery multiplication. In particular, compared to the previous version of tag tracing, the use of Montgomery multiplication entirely eliminates costly modular reductions and replaces these with much more efficient divisions by a suitable power of two.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Cryptography Discrete logarithm problem Pollard's Rho Tag Tracing Montgomery multiplication.
Contact author(s): madhurima_r @ isical ac in
palash @ isical ac in
History: 2021-01-14: revised; 2021-01-12: received; See all versions
Short URL: https://ia.cr/2021/043
License: CC BY

BibTeX

@misc{cryptoeprint:2021/043,
      author = {Madhurima Mukhopadhyay and Palash Sarkar},
      title = {Combining Montgomery Multiplication with Tag Tracing for the Pollard's Rho Algorithm in Prime Order Fields},
      howpublished = {Cryptology ePrint Archive, Paper 2021/043},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/043}},
      url = {https://eprint.iacr.org/2021/043}
}