Paper 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.

Note: Full version of the Asiacrypt 2012 paper

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Asiacrypt 2012
Keywords
Elliptic curve factorizationcofactorizationaddition chainstwisted Edwards curvesparallel architectures
Contact author(s)
joppe bos @ epfl ch
History
2012-09-07: revised
2012-02-23: received
See all versions
Short URL
https://ia.cr/2012/089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/089,
      author = {Joppe W.  Bos and Thorsten Kleinjung},
      title = {ECM at Work},
      howpublished = {Cryptology ePrint Archive, Paper 2012/089},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/089}},
      url = {https://eprint.iacr.org/2012/089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.