Paper 2021/043 Original: eprint.iacr.org/2021/043 ↗
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2021-01-14: last updated
- 2021-01-12: published
- Short URL
- https://ia.cr/2021/043
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2021/043}
}