Cryptology ePrint Archive: Report 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.
Category / Keywords: foundations / Cryptography, Discrete logarithm problem, Pollard's Rho, Tag Tracing, Montgomery multiplication.
Date: received 11 Jan 2021, last revised 14 Jan 2021
Contact author: madhurima_r at isical ac in, palash@isical ac in
Available format(s): PDF | BibTeX Citation
Version: 20210114:130158 (All versions of this report)
Short URL: ia.cr/2021/043
[ Cryptology ePrint archive ]