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