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