International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 12 January 2021

Madhurima Mukhopadhyay, Palash Sarkar
ePrint Report ePrint Report
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.

Additional news items may be found on the IACR news page.