An Algorithmic and Architectural Study on Montgomery Exponentiation in RNS
- 17 April 2012
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 61 (8), 1071-1083
- https://doi.org/10.1109/tc.2012.84
Abstract
The modular exponentiation on large numbers is computationally intensive. An effective way for performing this operation consists in using Montgomery exponentiation in the Residue Number System (RNS). This paper presents an algorithmic and architectural study of such exponentiation approach. From the algorithmic point of view, new and state-of-the-art opportunities that come from the reorganization of operations and precomputations are considered. From the architectural perspective, the design opportunities offered by well-known computer arithmetic techniques are studied, with the aim of developing an efficient arithmetic cell architecture. Furthermore, since the use of efficient RNS bases with a low Hamming weight are being considered with ever more interest, four additional cell architectures specifically tailored to these bases are developed and the tradeoff between benefits and drawbacks is carefully explored. An overall comparison among all the considered algorithmic approaches and cell architectures is presented, with the aim of providing the reader with an extensive overview of the Montgomery exponentiation opportunities in RNS.Keywords
This publication has 9 references indexed in Scilit:
- A General Approach for Improving RNS Montgomery Exponentiation Using Pre-processingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2011
- Selected RNS Bases for Modular MultiplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2009
- a full RNS implementation of RSAIEEE Transactions on Computers, 2004
- Implementation of RSA Algorithm Based on RNS Montgomery MultiplicationLecture Notes in Computer Science, 2001
- Modular multiplication and base extensions in residue number systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2001
- Modulo reduction in residue number systemsIEEE Transactions on Parallel and Distributed Systems, 1995
- Algorithmic Algebraic Number TheoryPublished by Cambridge University Press (CUP) ,1989
- Fast base extension using a redundant modulus in RNSIEEE Transactions on Computers, 1989
- Modular Multiplication Without Trial DivisionMathematics of Computation, 1985