Cryptology ePrint Archive: Report 2012/089

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-subtracting 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 (GPU). 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. Our ECM implementation on a GTX 580 GPU sets a new throughput record, outperforming the best GPU, CPU and FPGA results reported in literature.

Category / Keywords: Elliptic curve factorization, cofactorization, addition chains, twisted Edwards curves, parallel architectures

Publication Info: Asiacrypt 2012

Date: received 23 Feb 2012, last revised 7 Sep 2012

Contact author: joppe bos at epfl ch

Available format(s): PDF | BibTeX Citation

Note: Full version of the Asiacrypt 2012 paper

Version: 20120907:154344 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]