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 numberSingle Instruction Multiple DataCell processorElliptic curve methodInteger 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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.