Title: Solving a 112-bit prime elliptic curve discrete logarithm problem on game consoles using sloppy reduction
Authors: Joppe W. Bos; Marcelo E. Kaihara; Thorsten Kleinjung; Arjen K. Lenstra; Peter L. Montgomery
Addresses: Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne, Station 14, CH-1015 Lausanne, Switzerland. ' Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne, Station 14, CH-1015 Lausanne, Switzerland. ' Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne, Station 14, CH-1015 Lausanne, Switzerland. ' Laboratory for Cryptologic Algorithms, École Polytechnique Fédérale de Lausanne, Station 14, CH-1015 Lausanne, Switzerland. ' One Microsoft Way, Microsoft Research, Redmond, WA 98052, USA
Abstract: We describe a cell processor implementation of Pollard's rho method to solve discrete logarithms in groups of elliptic curves over prime fields. The implementation was used on a cluster of PlayStation 3 game consoles to set a new record. We present in detail the underlying single instruction multiple data modular arithmetic.
Keywords: elliptic curve discrete logarithm; Pollard rho method; cell processors; single instruction multiple data; SIMD; negation maps; game consoles; sloppy reduction; elliptic curves; prime fields; PlayStation 3.
DOI: 10.1504/IJACT.2012.045590
International Journal of Applied Cryptography, 2012 Vol.2 No.3, pp.212 - 228
Published online: 20 Sep 2014 *
Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article