Paper 2010/338

Efficient SIMD arithmetic modulo a Mersenne number

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


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"

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Mersenne numberSingle Instruction Multiple DataCell processorElliptic curve methodInteger factorization
Contact author(s)
joppe bos @ epfl ch
2010-11-23: last of 6 revisions
2010-06-13: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.