ECM at Work

Joppe W. Bos and Thorsten Kleinjung

Abstract

The performance of the elliptic curve method (ECM) for integer factorization plays an important role in the security assessment of RSA-based protocols as a cofactorization tool inside the number field sieve. The efficient arithmetic for Edwards curves found an application by speeding up ECM. We propose techniques based on generating and combining addition chains to optimize Edwards ECM in terms of both performance and memory requirements. This makes our approach very suitable for memory-constrained devices such as graphics processing units. For commonly used ECM parameters we are able to lower the required memory up to a factor 55 compared to the state-of-the-art Edwards ECM approach.

Details

Publication typeProceedings
Published inAsiacrypt 2012
URLhttp://eprint.iacr.org/2012/089
Pages467-484
Volume7658
SeriesLNCS
PublisherSpringer Verlag
> Publications > ECM at Work