Montgomery Multiplication on the CellReport as inadecuate

Montgomery Multiplication on the Cell - Download this document for free, or read online. Document in PDF available to download.

Presented at: 8th International Conference on Parallel Processing and Applied Mathematics, Wroclaw, POLAND, Sep 13-16, 2009 Published in: Parallel Processing And Applied Mathematics, Pt I (ISBN: 978-3-642-14389-2), vol. 6067, p. 477-485 Series: Lecture Notes in Computer Science Springer-Verlag New York, Ms Ingrid Cunningham, 175 Fifth Ave, New York, Ny 10010 Usa, 2010

A technique to speed up Montgomery multiplication targeted at the Synergistic Processor Elements (SPE) of the Cell Broadband Engine is proposed. The technique consists of splitting a number into four consecutive parts. These parts are placed one by one in each of the four element positions of a vector, representing columns in a 4-SIMD organization. This representation enables arithmetic to be performed in a 4-SIMD fashion. An implementation of the Montgomery multiplication using this technique is up to 2.47 times faster compared to an unrolled implementation of Montgomery multiplication, which is part of the IBM multi-precision math library, for odd moduli of length 160 to 2048 bits. The presented technique can also be applied to speed up Montgomery multiplication on other SIMD-architectures.

Keywords: Cell Broadband Engine ; Cryptology ; Computer Arithmetic ; Montgomery Multiplication ; Single Instruction Multiple Data (SIMD) Reference EPFL-CONF-172426doi:10.1007/978-3-642-14390-8_50View record in Web of Science

Author: Bos, Joppe Willem; Kaihara, Marcelo E.


Related documents