Montgomery Multiplication on the Cell

Joppe W. Bos and Marcelo E. Kaihara

Abstract

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.

Details

Publication typeInproceedings
Published inParallel Processing and Applied Mathematics – PPAM 2009
URLhttp://www.springerlink.com/content/n54806074h070241/
Pages477–485
Volume6067
SeriesLecture Notes in Computer Science
PublisherSpringer
> Publications > Montgomery Multiplication on the Cell