Cryptology ePrint Archive: Report 2010/338

Efficient SIMD arithmetic modulo a Mersenne number

Joppe W. Bos and Thorsten Kleinjung and 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.

Category / Keywords: Mersenne number, Single Instruction Multiple Data, Cell processor, Elliptic curve method, Integer factorization

Date: received 10 Jun 2010, last revised 23 Nov 2010

Contact author: joppe bos at epfl ch

Available format(s): PDF | BibTeX Citation

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

Version: 20101123:143817 (All versions of this report)

Short URL: ia.cr/2010/338

Discussion forum: Show discussion | Start new discussion