TY - GEN
T1 - ECM on graphics cards
AU - Bernstein, Daniel J.
AU - Chen, Tien Ren
AU - Cheng, Chen Mou
AU - Lange, Tanja
AU - Yang, Bo Yin
PY - 2009
Y1 - 2009
N2 - This paper reports record-setting performance for the ellipticcurve method of integer factorization: for example, 926.11 curves/second for ECM stage 1 with B1 = 8192 for 280-bit integers on a single PC. The state-of-the-art GMP-ECM software handles 124.71 curves/second for ECM stage 1 with B1 = 8192 for 280-bit integers using all four cores of a 2.4 GHz Core 2 Quad Q6600. The extra speed takes advantage of extra hardware, specifically two NVIDIA GTX 295 graphics cards, using a new ECM implementation introduced in this paper. Our implementation uses Edwards curves, relies on new parallel addition formulas, and is carefully tuned for the highly parallel GPU architecture. On a single GTX 295 the implementation performs 41.88 million modular multiplications per second for a general 280-bit modulus. GMP-ECM, using all four cores of a Q6600, performs 13.03 million modular multiplications per second. This paper also reports speeds on other graphics processors: for example, 2414 280-bit elliptic-curve scalar multiplications per second on an older NVIDIA 8800 GTS (G80), again for a general 280-bit modulus. For comparison, the CHES 2008 paper "Exploiting the Power of GPUs for Asymmetric Cryptography" reported 1412 elliptic-curve scalar multiplications per second on the same graphics processor despite having fewer bits in the scalar (224 instead of 280), fewer bits in the modulus (224 instead of 280), and a special modulus (2 224-296+1).
AB - This paper reports record-setting performance for the ellipticcurve method of integer factorization: for example, 926.11 curves/second for ECM stage 1 with B1 = 8192 for 280-bit integers on a single PC. The state-of-the-art GMP-ECM software handles 124.71 curves/second for ECM stage 1 with B1 = 8192 for 280-bit integers using all four cores of a 2.4 GHz Core 2 Quad Q6600. The extra speed takes advantage of extra hardware, specifically two NVIDIA GTX 295 graphics cards, using a new ECM implementation introduced in this paper. Our implementation uses Edwards curves, relies on new parallel addition formulas, and is carefully tuned for the highly parallel GPU architecture. On a single GTX 295 the implementation performs 41.88 million modular multiplications per second for a general 280-bit modulus. GMP-ECM, using all four cores of a Q6600, performs 13.03 million modular multiplications per second. This paper also reports speeds on other graphics processors: for example, 2414 280-bit elliptic-curve scalar multiplications per second on an older NVIDIA 8800 GTS (G80), again for a general 280-bit modulus. For comparison, the CHES 2008 paper "Exploiting the Power of GPUs for Asymmetric Cryptography" reported 1412 elliptic-curve scalar multiplications per second on the same graphics processor despite having fewer bits in the scalar (224 instead of 280), fewer bits in the modulus (224 instead of 280), and a special modulus (2 224-296+1).
KW - Edwards curves.
KW - Elliptic curves
KW - Elliptic-curve method of factorization
KW - Factorization
KW - Graphics processing unit
KW - Modular arithmetic
UR - https://www.scopus.com/pages/publications/67650679679
U2 - 10.1007/978-3-642-01001-9_28
DO - 10.1007/978-3-642-01001-9_28
M3 - 会议稿件
AN - SCOPUS:67650679679
SN - 3642010008
SN - 9783642010002
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 483
EP - 501
BT - Advances in Cryptology - EUROCRYPT 2009 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings
T2 - 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2009
Y2 - 26 April 2009 through 30 April 2009
ER -