Efficient SIMD arithmetic modulo a Mersenne number

Joppe W.  Bos; Thorsten Kleinjung; Arjen K.  Lenstra; Peter L.  Montgomery

Paper 2010/338

Efficient SIMD arithmetic modulo a Mersenne number

Joppe W. Bos, Thorsten Kleinjung, Arjen K. Lenstra, and Peter L. Montgomery

Abstract

This paper describes carry-less arithmetic operations modulo an integer $2^M - 1$ in the thousand-bit range, targeted at single instruction multiple data platforms and applications where overall throughput is the main performance criterion. Using an implementation on a cluster of PlayStation 3 game consoles a new record was set for the elliptic curve method for integer factorization.

Note: Formerly known as "Pushing the Limits of ECM"

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: Mersenne number Single Instruction Multiple Data Cell processor Elliptic curve method Integer factorization
Contact author(s): joppe bos @ epfl ch
History: 2010-11-23: last of 6 revisions; 2010-06-13: received; See all versions
Short URL: https://ia.cr/2010/338
License: CC BY

BibTeX

@misc{cryptoeprint:2010/338,
      author = {Joppe W.  Bos and Thorsten Kleinjung and Arjen K.  Lenstra and Peter L.  Montgomery},
      title = {Efficient {SIMD} arithmetic modulo a Mersenne number},
      howpublished = {Cryptology {ePrint} Archive, Paper 2010/338},
      year = {2010},
      url = {https://eprint.iacr.org/2010/338}
}