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

##### 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.

Available format(s)
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
CryptographyDiscrete logarithm problemPollard's RhoTag TracingMontgomery multiplication.
Contact author(s)
madhurima_r @ isical ac in
palash @ isical ac in
History
2021-01-14: revised
See all versions
Short URL
https://ia.cr/2021/043

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}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.