Cryptology ePrint Archive: Report 2013/519

Montgomery Multiplication Using Vector Instructions

Joppe W. Bos and Peter L. Montgomery and Daniel Shumow and Gregory M. Zaverucha

Abstract: In this paper we present a parallel approach to compute interleaved Montgomery multiplication. This approach is particularly suitable to be computed on 2-way single instruction, multiple data platforms as can be found on most modern computer architectures in the form of vector instruction set extensions. We have implemented this approach for tablet devices which run the x86 architecture (Intel Atom Z2760) using SSE2 instructions as well as devices which run on the ARM platform (Qualcomm MSM8960, NVIDIA Tegra 3 and 4) using NEON instructions. When instantiating modular exponentiation with this parallel version of Montgomery multiplication we observed a performance increase of more than a factor of 1.5 compared to the sequential implementation in OpenSSL for the classical arithmetic logic unit on the Atom platform for 2048-bit moduli.

Category / Keywords: implementation / Montgomery multiplication, SIMD, software implementation, vector instructions

Original Publication (with minor differences): SAC 2013

Date: received 20 Aug 2013

Contact author: jbos at microsoft com

Available format(s): PDF | BibTeX Citation

Version: 20130821:012236 (All versions of this report)

Short URL: ia.cr/2013/519

Discussion forum: Show discussion | Start new discussion