[Resource Topic] 2021/043: Combining Montgomery Multiplication with Tag Tracing for the Pollard's Rho Algorithm in Prime Order Fields

Welcome to the resource topic for 2021/043

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

Authors: Madhurima Mukhopadhyay, 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.

ePrint: https://eprint.iacr.org/2021/043

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .